-
Notifications
You must be signed in to change notification settings - Fork 0
/
sortition.go
119 lines (101 loc) · 2.78 KB
/
sortition.go
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
package sortition
import (
"encoding/hex"
"errors"
utils "github.com/tendermint/tendermint/vrf/ed25519"
"math/big"
)
var (
ErrInvalidParams = errors.New("invalide params")
HashMax, _, _ = new(big.Float).Parse("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 16)
)
var (
// cache to store binomial probabilities
// key: n+p, value: related probabilities (0~n)
probCache = make(map[float64]([]float64), 5)
)
// Simplified sortition algorithm implementation
// In original design, each candidate need to generate verifiable random
// based on their secret key before sortition. In this case, we need a
// round of consensus to make sure all candidates are honest.
// In the simplied vesion, we'll use ordinary SHA3-256 to generate random
// which is public and fair to everyone. However, candidate's public key
// and each block's VRF seed will be used as entropy sources.
//
// Params
// key: candidate's public key
// seed: block's VRF seed
// t: each subuser's stake
// s: size of subuser committee (to be nominated)
// w: current candidate's stake
// W: all candidates' total stake
// Returns
// hash: generated random
// j: nominated subuser number
func Sortition(key []byte, seed []byte, t, s, w, W int64) (hash []byte, j uint) {
hash = utils.Sha3256(key, seed)
tao := t * s
p := float64(tao) / float64(W)
j = 0
n := uint(w / t)
hashVal, _, _ := new(big.Float).Parse(hex.EncodeToString(hash), 16)
if hashVal != nil {
lot, _ := new(big.Float).Quo(hashVal, HashMax).Float64()
section := float64(0)
for ; j <= n; j++ {
section, _ = cumulativeBinomial(p, n, j)
if lot <= section {
break
}
}
//fmt.Printf("[j=%d]lot: %.2f, section: %.2f, hash: %v\n", j, lot, section, new(big.Int).SetBytes(hash))
}
return
}
func power(x float64, n uint) float64 {
if n == 0 {
return 1.0
}
return x * power(x, n - 1)
}
func factorial(n uint) uint {
if n == 0 || n == 1 {
return 1
}
return n * factorial(n - 1)
}
func singleBinomial(p float64, n, k uint) (float64, error) {
if p <= 0 || p >= 1 || k > n {
return 0, ErrInvalidParams
}
a := factorial(n)
b := power(p, k)
c := power(1 - p, n - k)
num := float64(a) * b * c
den := float64(factorial(k) * factorial(n - k))
return num / den, nil
}
func binomial(p float64, n uint) []float64 {
probs := []float64{}
for i := uint(0); i <= n; i++ {
pi, _ := singleBinomial(p, n, i)
probs = append(probs, pi)
}
return probs
}
func cumulativeBinomial(p float64, n, k uint) (float64, error) {
if p <= 0 || p >= 1 || k > n {
return 0, ErrInvalidParams
}
// use n+p as unique key for probCache
key := float64(n) + p
if _, ok := probCache[key]; !ok {
probCache[key] = binomial(p, n)
}
probs := probCache[key]
sum := 0.0
for i := uint(0); i <= k; i++ {
sum += probs[i]
}
return sum, nil
}