contract/system/vprt.go
package system
import (
"bytes"
"container/list"
"encoding/binary"
"errors"
"fmt"
"io"
"math/big"
"math/rand"
"reflect"
"github.com/aergoio/aergo-lib/log"
"github.com/aergoio/aergo/v2/internal/enc/base58"
"github.com/aergoio/aergo/v2/state/statedb"
"github.com/aergoio/aergo/v2/types"
"github.com/aergoio/aergo/v2/types/dbkey"
rb "github.com/emirpasic/gods/trees/redblacktree"
jsoniter "github.com/json-iterator/go"
"github.com/sanity-io/litter"
)
// ********************************** WARNING **********************************
// All the functions and the methods below must be properly synchronized by
// acquiring the chain lock (chain.Lock / chain.Unlock) when they are called.
// *****************************************************************************
const (
vprMax = uint32(50000)
// vprBucketsMax must be smaller than 256. A bigger number is regarded as
// 256.
vprBucketsMax = 71
)
var (
ErrNoVotingRewardWinner = errors.New("voting reward: no winner")
ErrNoVotingRewardRank = errors.New("voting reward rank: not initialized")
zeroValue = types.NewZeroAmount()
million = types.NewAmount(1e6, types.Aer) // 1,000,000 Aer
annualRewardM = types.NewAmount(5045760000, types.Gaer) // 5,045,760,000 Gaer
annualReward = new(big.Int).Mul(annualRewardM, million) // 5,045,760 AERGO
oneYIS = new(big.Int).SetUint64(365 * 24 * 60 * 60)
defaultReward = new(big.Int).Div(annualReward, oneYIS) // 0.16 AERGO per sec
binSize = types.NewAmount(1e4, types.Aergo) // 10,000 AERGO
votingPowerRank *vpr
vprLogger = log.NewLogger("vpr")
jsonIter = jsoniter.ConfigCompatibleWithStandardLibrary
)
type dataSetter interface {
SetData(key, value []byte) error
}
type dataGetter interface {
GetData(key []byte) ([]byte, error)
}
// InitVotingPowerRank reads the stored data from s and initializes the Voting
// Power Rank, which contains each voters's voting power.
func InitVotingPowerRank(s dataGetter) (err error) {
votingPowerRank, err = loadVpr(s)
return
}
type votingPower struct {
id types.AccountID
addr types.Address
power *big.Int
}
func newVotingPower(addr []byte, id types.AccountID, pow *big.Int) *votingPower {
return &votingPower{addr: addr, id: id, power: pow}
}
func (vp *votingPower) getAddr() []byte {
return vp.addr
}
func (vp *votingPower) setAddr(addr []byte) {
vp.addr = addr
}
func (vp *votingPower) getID() types.AccountID {
return vp.id
}
func (vp *votingPower) idBytes() []byte {
return vp.id[:]
}
func (vp *votingPower) setID(id types.AccountID) {
vp.id = id
}
func (vp *votingPower) getPower() *big.Int {
return vp.power
}
func (vp *votingPower) setPower(pow *big.Int) {
vp.power = pow
}
func (vp *votingPower) cmp(pow *big.Int) int {
return vp.getPower().Cmp(pow)
}
func (vp *votingPower) lt(rhs *votingPower) bool {
return vp.cmp(rhs.getPower()) < 0
}
func (vp *votingPower) le(rhs *votingPower) bool {
return vp.lt(rhs) || vp.cmp(rhs.getPower()) == 0
}
func (vp *votingPower) isZero() bool {
return vp.getPower().Cmp(zeroValue) == 0
}
func (vp *votingPower) marshal() []byte {
var buf bytes.Buffer
// Account ID
buf.Write(vp.idBytes()) // 32 bytes
// Address
binary.Write(&buf, binary.LittleEndian, uint16(len(vp.addr)))
buf.Write(vp.addr)
// Voting Power
pwr := vp.getPower().Bytes()
binary.Write(&buf, binary.LittleEndian, uint16(len(pwr)))
buf.Write(pwr)
return buf.Bytes()
}
func (vp *votingPower) unmarshal(b []byte) uint32 {
var sz1, sz2 uint16
r := bytes.NewReader(b)
r.Seek(int64(32), 0)
binary.Read(r, binary.LittleEndian, &sz1)
// <Accound ID (32)> + <address length (2)> + <address>
r.Seek(int64(32+2+sz1), 0)
binary.Read(r, binary.LittleEndian, &sz2)
vp.setID(types.AccountID(types.ToHashID(b[:32])))
vp.setAddr(b[34 : 34+sz1])
if int(36+sz1+sz2) < len(b) {
vp.setPower(new(big.Int).SetBytes(b[36+sz1 : 36+sz1+sz2]))
} else {
vp.setPower(new(big.Int).SetBytes(b[36+sz1:]))
}
return 36 + uint32(sz1) + uint32(sz2)
}
func (vp *votingPower) toJSON() ([]byte, error) {
b, err := jsonIter.Marshal(&struct {
Address string
Power string
}{types.EncodeAddress(vp.getAddr()), vp.getPower().String()})
if err != nil {
return nil, err
}
return b, nil
}
type vprStore struct {
buckets map[uint8]*list.List
cmp func(lhs *votingPower, rhs *votingPower) int
}
func newVprStore(bucketsMax uint32) *vprStore {
return &vprStore{
buckets: make(map[uint8]*list.List, bucketsMax),
cmp: func(lhs *votingPower, rhs *votingPower) int {
return bytes.Compare(lhs.idBytes(), rhs.idBytes())
},
}
}
func (b *vprStore) equals(rhs *vprStore) bool {
if !reflect.DeepEqual(b.buckets, rhs.buckets) {
return false
}
return true
}
func (b *vprStore) update(vp *votingPower) (idx uint8) {
var (
id = vp.getID()
pow = vp.getPower()
)
idx = getBucketIdx(id)
var (
bu *list.List
exist bool
)
if bu, exist = b.buckets[idx]; !exist {
bu = list.New()
b.buckets[idx] = bu
}
v := remove(bu, id)
if vp.isZero() {
// A zero power voter must be removed.
return
}
if v != nil {
v.setPower(pow)
} else {
v = vp
}
orderedListAdd(bu, v,
func(e *list.Element) bool {
ind := b.cmp(toVotingPower(e), v)
return ind <= 0
},
)
return
}
type predicate func(e *list.Element) bool
func search(l *list.List, match func(e *list.Element) bool) *list.Element {
for e := l.Front(); e != nil; e = e.Next() {
if match(e) {
return e
}
}
return nil
}
func orderedListMove(l *list.List, e *list.Element, match predicate) {
if m := search(l, match); m != nil {
l.MoveBefore(e, m)
} else {
l.MoveToBack(e)
}
}
func orderedListAdd(l *list.List, e *votingPower, match predicate) *list.Element {
var voter *list.Element
if m := search(l, match); m != nil {
voter = l.InsertBefore(e, m)
} else {
voter = l.PushBack(e)
}
return voter
}
func (b *vprStore) addTail(i uint8, vp *votingPower) {
var l *list.List
if l = b.buckets[i]; l == nil {
l = list.New()
b.buckets[i] = l
}
l.PushBack(vp)
}
func (b *vprStore) write(s dataSetter, i uint8) error {
var buf bytes.Buffer
l := b.buckets[i]
for e := l.Front(); e != nil; e = e.Next() {
buf.Write(toVotingPower(e).marshal())
}
return s.SetData(dbkey.SystemVpr(i), buf.Bytes())
}
func (b *vprStore) read(s dataGetter, i uint8) ([]*votingPower, error) {
buf, err := s.GetData(dbkey.SystemVpr(i))
if err != nil {
return nil, err
}
vps := make([]*votingPower, 0, 10)
for off := 0; off < len(buf); {
vp := &votingPower{}
off += int(vp.unmarshal(buf[off:]))
vps = append(vps, vp)
}
return vps, nil
}
func remove(bu *list.List, id types.AccountID) *votingPower {
for e := bu.Front(); e != nil; e = e.Next() {
if v := toVotingPower(e); id == v.getID() {
return bu.Remove(e).(*votingPower)
}
}
return nil
}
func getBucketIdx(addr types.AccountID) uint8 {
return uint8(addr[0]) % vprBucketsMax
}
func (b *vprStore) getBucket(addr types.AccountID) *list.List {
if b, exist := b.buckets[getBucketIdx(addr)]; exist {
return b
}
return nil
}
type topVoters struct {
members *rb.Tree
max uint32
powers map[types.AccountID]*votingPower
}
func newTopVoters(max uint32) *topVoters {
cmp := func(lhs, rhs interface{}) int {
var (
l = lhs.(*votingPower)
r = rhs.(*votingPower)
)
pwrInd := l.getPower().Cmp(r.getPower())
if pwrInd == 0 {
return -bytes.Compare(l.idBytes(), r.idBytes())
}
return -pwrInd
}
return &topVoters{
members: rb.NewWith(cmp),
max: max,
powers: make(map[types.AccountID]*votingPower),
}
}
func (tv *topVoters) equals(rhs *topVoters) bool {
if !reflect.DeepEqual(tv.powers, rhs.powers) {
return false
}
if !reflect.DeepEqual(tv.members.Keys(), rhs.members.Keys()) {
return false
}
if tv.max != rhs.max {
return false
}
return true
}
func (tv *topVoters) Count() int {
return len(tv.powers)
}
func (tv *topVoters) get(id types.AccountID) *votingPower {
return tv.powers[id]
}
func (tv *topVoters) set(id types.AccountID, v *votingPower) {
tv.powers[id] = v
}
func (tv *topVoters) del(id types.AccountID) {
delete(tv.powers, id)
}
func (tv *topVoters) getVotingPower(addr types.AccountID) *votingPower {
return tv.powers[addr]
}
func (tv *topVoters) powerOf(addr types.AccountID) *big.Int {
if vp := tv.getVotingPower(addr); vp != nil {
return vp.getPower()
}
return nil
}
func (tv *topVoters) lowest() *votingPower {
lowest := tv.members.Right()
if lowest == nil {
return nil
}
return lowest.Value.(*votingPower)
}
func (tv *topVoters) update(v *votingPower) (vp *votingPower) {
// XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
// TODO: Maintain len(tv.powers) <= tv.max
//
// * Rejection & Eviction Rule:
//
// 1. Reject if the new voter has a voting power lesser than the lowest.
//
// 2. Evict the lowest if the new voter has a voting power larger than
// anyone among the current voting power rankers.
//
// 3. Randomly select & evict one among the lowest voters if the new voter
// has the same voting power as the lowest voter.
//
// -------------------------------------------------------------------------
//
// ISSUE - There exists some unfair case as follows: The VPR slots are
// fully occupied (len(tv.powers) == tv.max) so that a voter A is rejected
// by the rule above. Afterwards, one voter cancels his staking and is
// removed from the VPR. In such a situtation, any voter cating a vote will
// be unconditionally included into the VPR since one slot is available for
// him even if his voting power is less than the aforementioned voter A.
// XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
if vp = tv.get(v.getID()); vp != nil {
tv.members.Remove(vp)
if vp.isZero() {
tv.del(vp.getID())
} else {
vp.setPower(v.getPower())
tv.members.Put(vp, vp)
}
} else {
vp = v
tv.members.Put(v, v)
tv.set(v.getID(), v)
}
return
}
func (tv *topVoters) dump(w io.Writer, topN int) error {
if tv == nil {
fmt.Fprintf(w, "nothing to dump!")
return nil
}
endingIndex := func() int {
size := tv.members.Size()
if topN < size && topN > 0 {
return topN - 1
}
return size - 1
}
end := endingIndex()
fmt.Fprint(w, "[\n")
for i, m := range tv.members.Values() {
if topN > 0 && i >= topN {
break
}
if vp, ok := m.(*votingPower); ok {
if b, err := vp.toJSON(); err == nil {
fmt.Fprintf(w, "%s", string(b))
if i != end {
fmt.Fprint(w, ",\n")
}
} else {
return err
}
} else {
vprLogger.Error().Str("content", litter.Sdump(m)).Msg("invalid type of member")
}
}
fmt.Fprint(w, "\n]\n")
return nil
}
func (tv *topVoters) addVotingPower(id types.AccountID, delta *deltaVP) *votingPower {
vp := tv.getVotingPower(id)
if vp != nil {
pwr := vp.getPower()
pwr.Add(pwr, delta.getAmount())
} else {
vp = newVotingPower(delta.getAddr(), id, delta.getAmount())
}
return tv.update(vp)
}
// Voters Power Ranking (VPR)
type vpr struct {
voters *topVoters
store *vprStore
totalPower *big.Int
lowest *votingPower
changes map[types.AccountID]*deltaVP // temporary buffer for update
}
func newVpr() *vpr {
return &vpr{
voters: newTopVoters(vprMax),
store: newVprStore(vprBucketsMax),
totalPower: new(big.Int),
changes: make(map[types.AccountID]*deltaVP, vprMax),
}
}
func loadVpr(s dataGetter) (*vpr, error) {
v := newVpr()
for i := uint8(0); i < vprBucketsMax; i++ {
var (
vps []*votingPower
err error
)
if vps, err = v.store.read(s, i); err != nil {
return nil, err
}
for _, vp := range vps {
rv := v.voters.update(vp)
v.store.addTail(i, rv)
v.updateLowest(vp)
v.addTotal(rv.getPower())
}
}
return v, nil
}
func (v *vpr) equals(rhs *vpr) bool {
if !reflect.DeepEqual(v.getTotalPower(), rhs.getTotalPower()) {
return false
}
if !reflect.DeepEqual(v.getLowest(), rhs.getLowest()) {
return false
}
if !v.voters.equals(rhs.voters) {
return false
}
if len(v.changes) != len(v.changes) {
return false
}
return true
}
func (v *vpr) getTotalPower() *big.Int {
if v == nil {
return nil
}
return new(big.Int).Set(v.totalPower)
}
func (v *vpr) getLowest() *votingPower {
return v.lowest
}
func (v *vpr) updateLowest(vp *votingPower) {
if vp.isZero() {
v.resetLowest()
return
}
if v.lowest == nil {
v.lowest = vp
} else if vp.lt(v.lowest) {
v.lowest = vp
}
}
func (v *vpr) setLowest(vp *votingPower) {
v.lowest = vp
}
func (v *vpr) addTotal(delta *big.Int) {
total := v.totalPower
total.Add(total, delta)
}
func (v *vpr) votingPowerOf(addr types.AccountID) *big.Int {
return v.voters.powerOf(addr)
}
func (v *vpr) prepare(id types.AccountID, addr types.Address, fn func(lhs *big.Int)) {
if _, exist := v.changes[id]; !exist {
v.changes[id] = newDeltaVP(addr, new(big.Int))
}
// Each entry of v.changes corresponds to the change (increment or
// decrement) of voting power. It is added to later by calling the v.apply
// method.
ch := v.changes[id]
fn(ch.getAmount())
}
func (v *vpr) add(id types.AccountID, addr []byte, power *big.Int) {
if v == nil || power == nil || power.Cmp(zeroValue) == 0 {
return
}
v.prepare(id, addr,
func(lhs *big.Int) {
if vprLogger.IsDebugEnabled() {
vprLogger.Debug().
Str("op", "add").
Str("addr", base58.Encode(addr)).
Str("orig", lhs.String()).
Str("delta", power.String()).
Msg("prepare voting power change")
}
lhs.Add(lhs, power)
},
)
}
func (v *vpr) sub(id types.AccountID, addr []byte, power *big.Int) {
if v == nil || v.voters.powers[id] == nil {
return
}
v.prepare(id, addr,
func(lhs *big.Int) {
if vprLogger.IsDebugEnabled() {
vprLogger.Debug().
Str("op", "sub").
Str("addr", base58.Encode(addr)).
Str("orig", lhs.String()).
Str("delta", power.String()).
Msg("prepare voting power change")
}
lhs.Sub(lhs, power)
},
)
}
func (v *vpr) apply(s *statedb.ContractState) (int, error) {
if v == nil || len(v.changes) == 0 {
return 0, nil
}
var (
nApplied = 0
updRows = make(map[uint8]interface{})
)
for id, delta := range v.changes {
if delta.cmp(zeroValue) != 0 {
vp := v.voters.addVotingPower(id, delta)
if s != nil {
i := v.store.update(vp)
if _, exist := updRows[i]; !exist {
updRows[i] = struct{}{}
}
}
v.updateLowest(vp)
v.addTotal(delta.getAmount())
delete(v.changes, id)
// TODO: Remove a victim chosen above from the VPR bucket.
nApplied++
}
}
for i := range updRows {
if err := v.store.write(s, i); err != nil {
return 0, err
}
}
return nApplied, nil
}
func (v *vpr) resetLowest() {
v.setLowest(v.voters.lowest())
}
func PickVotingRewardWinner(seed int64) (types.Address, error) {
return votingPowerRank.pickVotingRewardWinner(seed)
}
func (v *vpr) pickVotingRewardWinner(seed int64) (types.Address, error) {
if v == nil {
return nil, ErrNoVotingRewardRank
}
if v.getTotalPower().Cmp(zeroValue) == 0 {
return nil, ErrNoVotingRewardWinner
}
totalVp := v.getTotalPower()
r := new(big.Int).Rand(
rand.New(rand.NewSource(seed)),
totalVp)
for i := uint8(0); i < vprBucketsMax; i++ {
if l := v.store.buckets[i]; l != nil && l.Len() > 0 {
for e := l.Front(); e != nil; e = e.Next() {
vp := toVotingPower(e)
if r.Sub(r, vp.getPower()).Cmp(zeroValue) < 0 {
winner := vp.getAddr()
if vprLogger.IsDebugEnabled() {
vprLogger.Debug().
Str("total voting power", totalVp.String()).
Str("addr", base58.Encode(winner)).
Msg("pick voting reward winner")
}
return winner, nil
}
}
}
}
return nil, ErrNoVotingRewardWinner
}
func toVotingPower(e *list.Element) *votingPower {
return e.Value.(*votingPower)
}
type deltaVP struct {
addr_ types.Address
amount *big.Int
}
func newDeltaVP(addr []byte, amount *big.Int) *deltaVP {
return &deltaVP{addr_: addr, amount: amount}
}
func (dv *deltaVP) getAddr() types.Address {
return dv.addr_
}
func (dv *deltaVP) getAmount() *big.Int {
return dv.amount
}
func (dv *deltaVP) cmp(rhs *big.Int) int {
return dv.getAmount().Cmp(rhs)
}
func GetVotingRewardAmount() *big.Int {
return defaultReward
}
func GetTotalVotingPower() *big.Int {
return votingPowerRank.getTotalPower()
}
func DumpVotingPowerRankers(w io.Writer, topN int) error {
if votingPowerRank == nil {
return errors.New("not supported")
}
return votingPowerRank.voters.dump(w, topN)
}