1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
|
// Copyright (C) 2019-2023 Algorand, Inc.
// This file is part of go-algorand
//
// go-algorand is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// go-algorand 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 Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with go-algorand. If not, see <https://www.gnu.org/licenses/>.
package ledgercore
import (
"fmt"
"sync"
"github.com/algorand/go-deadlock"
"github.com/algorand/go-algorand/config"
"github.com/algorand/go-algorand/crypto"
"github.com/algorand/go-algorand/crypto/merklearray"
"github.com/algorand/go-algorand/crypto/merklesignature"
"github.com/algorand/go-algorand/crypto/stateproof"
"github.com/algorand/go-algorand/data/basics"
"github.com/algorand/go-algorand/data/bookkeeping"
)
// OnlineAccountsFetcher captures the functionality of querying online accounts status
type OnlineAccountsFetcher interface {
// TopOnlineAccounts returns the top n online accounts, sorted by their normalized
// balance and address, whose voting keys are valid in voteRnd. See the
// normalization description in AccountData.NormalizedOnlineBalance().
TopOnlineAccounts(rnd basics.Round, voteRnd basics.Round, n uint64, params *config.ConsensusParams, rewardsLevel uint64) (topOnlineAccounts []*OnlineAccount, totalOnlineStake basics.MicroAlgos, err error)
}
// LedgerForSPBuilder captures the functionality needed for the creation of the cryptographic state proof builder.
type LedgerForSPBuilder interface {
VotersForStateProof(rnd basics.Round) (*VotersForRound, error)
BlockHdr(basics.Round) (bookkeeping.BlockHeader, error)
}
// VotersCommitListener represents an object that needs to get notified on commit stages in the voters tracker.
type VotersCommitListener interface {
// OnPrepareVoterCommit gives the listener the opportunity to backup VotersForRound data related to rounds (oldBase, newBase] before it is being removed.
// The implementation should log any errors that might occur.
OnPrepareVoterCommit(oldBase basics.Round, newBase basics.Round, voters LedgerForSPBuilder)
}
// VotersForRound tracks the top online voting accounts as of a particular
// round, along with a Merkle tree commitment to those voting accounts.
type VotersForRound struct {
// Because it can take some time to compute the top participants and the
// corresponding Merkle tree, the votersForRound is constructed in
// the background. This means that fields (participants, adddToPos,
// tree, and totalWeight) could be nil/zero while a background thread
// is computing them. Once the fields are set, however, they are
// immutable, and it is no longer necessary to acquire the lock.
//
// If an error occurs while computing the tree in the background,
// loadTreeError might be set to non-nil instead. That also finalizes
// the state of this VotersForRound.
mu deadlock.Mutex
cond *sync.Cond
loadTreeError error
// Proto is the ConsensusParams for the round whose balances are reflected
// in participants.
Proto config.ConsensusParams
// Participants is the array of top StateProofTopVoters online accounts
// in this round, sorted by normalized balance (to make sure heavyweight
// accounts are biased to the front).
Participants basics.ParticipantsArray
// AddrToPos specifies the position of a given account address (if present)
// in the Participants array. This allows adding a vote from a given account
// to the certificate builder.
AddrToPos map[basics.Address]uint64
// Tree is a constructed Merkle tree of the Participants array.
Tree *merklearray.Tree
// TotalWeight is the sum of the weights from the Participants array.
TotalWeight basics.MicroAlgos
}
// MakeVotersForRound create a new VotersForRound object and initialize it's cond.
func MakeVotersForRound() *VotersForRound {
vr := &VotersForRound{}
vr.cond = sync.NewCond(&vr.mu)
return vr
}
func createStateProofParticipant(stateProofID *merklesignature.Commitment, money basics.MicroAlgos) basics.Participant {
var retPart basics.Participant
retPart.Weight = money.ToUint64()
// Some accounts might not have StateProof keys commitment. As a result,
// the commitment would be an array filled with zeroes: [0x0...0x0].
// Since the commitment is created using the subset-sum hash function, for which the
// value [0x0..0x0] might be known, we avoid using such empty commitments.
// We replace it with a commitment for zero keys..
if stateProofID.IsEmpty() {
copy(retPart.PK.Commitment[:], merklesignature.NoKeysCommitment[:])
} else {
copy(retPart.PK.Commitment[:], stateProofID[:])
}
// KeyLifetime is set as a default value here (256) as the currently registered StateProof keys do not have a KeyLifetime value associated with them.
// In order to support changing the KeyLifetime in the future, we would need to update the Keyreg transaction and replace the value here with the one
// registered by the Account.
retPart.PK.KeyLifetime = merklesignature.KeyLifetimeDefault
return retPart
}
// LoadTree loads the participation tree and other required fields, using the provided OnlineAccountsFetcher.
func (tr *VotersForRound) LoadTree(onlineAccountsFetcher OnlineAccountsFetcher, hdr bookkeeping.BlockHeader) error {
r := hdr.Round
// stateProofRound is the block that we expect to form a state proof for,
// using the balances from round r.
stateProofRound := r + basics.Round(tr.Proto.StateProofVotersLookback+tr.Proto.StateProofInterval)
top, totalOnlineWeight, err := onlineAccountsFetcher.TopOnlineAccounts(r, stateProofRound, tr.Proto.StateProofTopVoters, &tr.Proto, hdr.RewardsLevel)
if err != nil {
return err
}
participants := make(basics.ParticipantsArray, len(top))
addrToPos := make(map[basics.Address]uint64)
for i, acct := range top {
var ot basics.OverflowTracker
rewards := basics.PendingRewards(&ot, tr.Proto, acct.MicroAlgos, acct.RewardsBase, hdr.RewardsLevel)
money := ot.AddA(acct.MicroAlgos, rewards)
if ot.Overflowed {
return fmt.Errorf("votersTracker.LoadTree: overflow adding rewards %d + %d", acct.MicroAlgos, rewards)
}
participants[i] = createStateProofParticipant(&acct.StateProofID, money)
addrToPos[acct.Address] = uint64(i)
}
tree, err := merklearray.BuildVectorCommitmentTree(participants, crypto.HashFactory{HashType: stateproof.HashType})
if err != nil {
return err
}
tr.mu.Lock()
tr.AddrToPos = addrToPos
tr.Participants = participants
tr.TotalWeight = totalOnlineWeight
tr.Tree = tree
tr.cond.Broadcast()
tr.mu.Unlock()
return nil
}
// BroadcastError broadcasts the error
func (tr *VotersForRound) BroadcastError(err error) {
tr.mu.Lock()
tr.loadTreeError = err
tr.cond.Broadcast()
tr.mu.Unlock()
}
// Wait waits for the tree to get constructed.
func (tr *VotersForRound) Wait() error {
tr.mu.Lock()
defer tr.mu.Unlock()
for tr.Tree == nil {
if tr.loadTreeError != nil {
return tr.loadTreeError
}
tr.cond.Wait()
}
return nil
}
|
