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
|
// Copyright (C) 2019-2024 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 stateproof
import (
"encoding/binary"
"math/big"
"golang.org/x/crypto/sha3"
"github.com/algorand/go-algorand/crypto"
"github.com/algorand/go-algorand/protocol"
)
// The coinChoiceSeed defines the randomness seed that will be given to an XOF function. This will be used for choosing
// the index of the coin to reveal as part of the state proof.
type coinChoiceSeed struct {
// the ToBeHashed function should be updated when fields are added to this structure
version byte
partCommitment crypto.GenericDigest
lnProvenWeight uint64
sigCommitment crypto.GenericDigest
signedWeight uint64
data MessageHash
}
// ToBeHashed returns a binary representation of the coinChoiceSeed structure.
// Since this code is also implemented as a circuit in the stateproof SNARK prover we can't use
// msgpack encoding since it may result in a variable length byte slice.
// Alternatively, we serialize the fields in the structure in a specific format.
func (cc *coinChoiceSeed) ToBeHashed() (protocol.HashID, []byte) {
var signedWtAsBytes [8]byte
binary.LittleEndian.PutUint64(signedWtAsBytes[:], cc.signedWeight)
var lnProvenWtAsBytes [8]byte
binary.LittleEndian.PutUint64(lnProvenWtAsBytes[:], cc.lnProvenWeight)
coinChoiceBytes := make([]byte, 0, 1+len(cc.partCommitment)+len(lnProvenWtAsBytes)+len(cc.sigCommitment)+len(signedWtAsBytes)+len(cc.data))
coinChoiceBytes = append(coinChoiceBytes, cc.version)
coinChoiceBytes = append(coinChoiceBytes, cc.partCommitment...)
coinChoiceBytes = append(coinChoiceBytes, lnProvenWtAsBytes[:]...)
coinChoiceBytes = append(coinChoiceBytes, cc.sigCommitment...)
coinChoiceBytes = append(coinChoiceBytes, signedWtAsBytes[:]...)
coinChoiceBytes = append(coinChoiceBytes, cc.data[:]...)
return protocol.StateProofCoin, coinChoiceBytes
}
// coinGenerator is used for extracting "randomized" 64 bits for coin flips
type coinGenerator struct {
shkContext sha3.ShakeHash
signedWeight uint64
threshold *big.Int
}
// makeCoinGenerator creates a new CoinHash context.
// it is used for squeezing 64 bits for coin flips.
// the function inits the XOF function in the following manner
// Shake(coinChoiceSeed)
// we extract 64 bits from shake for each coin flip and divide it by signedWeight
func makeCoinGenerator(choice *coinChoiceSeed) coinGenerator {
choice.version = VersionForCoinGenerator
rep := crypto.HashRep(choice)
shk := sha3.NewShake256()
shk.Write(rep) // hash.Hash interface's Write may panic, but does not return error
threshold := prepareRejectionSamplingThreshold(choice.signedWeight)
return coinGenerator{shkContext: shk, signedWeight: choice.signedWeight, threshold: threshold}
}
func prepareRejectionSamplingThreshold(signedWeight uint64) *big.Int {
// we use rejection sampling in order to have a uniform random coin in [0,signedWeight).
// use b bits (b=64) per attempt.
// define k = roundDown( 2^b / signedWeight ) implemented as (2^b div signedWeight)
// and threshold = k*signedWeight
threshold := &big.Int{}
threshold.SetUint64(1)
const numberOfBitsPerAttempt = 64
threshold.Lsh(threshold, numberOfBitsPerAttempt)
signedWt := &big.Int{}
signedWt.SetUint64(signedWeight)
// k = 2^b / signedWeight
threshold.Div(threshold, signedWt)
threshold.Mul(threshold, signedWt)
return threshold
}
// getNextCoin returns the next 64bits integer which represents a number between [0,signedWeight)
func (cg *coinGenerator) getNextCoin() uint64 {
// take b bits from the XOF and generate an integer z.
// we accept the sample if z < threshold
// else, we reject the sample and repeat the process.
var randNumFromXof uint64
for {
var shakeDigest [8]byte
cg.shkContext.Read(shakeDigest[:]) //nolint:errcheck // ShakeHash.Read never returns error
randNumFromXof = binary.LittleEndian.Uint64(shakeDigest[:])
z := &big.Int{}
z.SetUint64(randNumFromXof)
if z.Cmp(cg.threshold) == -1 {
break
}
}
return randNumFromXof % cg.signedWeight
}
|
