-
Notifications
You must be signed in to change notification settings - Fork 5
/
naive.go
105 lines (92 loc) · 3.2 KB
/
naive.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
package sync_contribution
import (
"github.com/theQRL/qrysm/v4/crypto/dilithium"
v2 "github.com/theQRL/qrysm/v4/proto/prysm/v1alpha1"
"github.com/theQRL/qrysm/v4/proto/prysm/v1alpha1/attestation/aggregation"
)
// naiveSyncContributionAggregation aggregates naively, without any complex algorithms or optimizations.
// Note: this is currently a naive implementation to the order of O(mn^2).
func naiveSyncContributionAggregation(contributions []*v2.SyncCommitteeContribution) ([]*v2.SyncCommitteeContribution, error) {
if len(contributions) <= 1 {
return contributions, nil
}
// Naive aggregation. O(n^2) time.
for i, a := range contributions {
if i >= len(contributions) {
break
}
for j := i + 1; j < len(contributions); j++ {
b := contributions[j]
if o, err := a.AggregationBits.Overlaps(b.AggregationBits); err != nil {
return nil, err
} else if !o {
var err error
a, err = aggregate(a, b)
if err != nil {
return nil, err
}
// Delete b
contributions = append(contributions[:j], contributions[j+1:]...)
j--
contributions[i] = a
}
}
}
// Naive deduplication of identical contributions. O(n^2) time.
for i, a := range contributions {
for j := i + 1; j < len(contributions); j++ {
b := contributions[j]
if a.AggregationBits.Len() != b.AggregationBits.Len() {
continue
}
if c, err := a.AggregationBits.Contains(b.AggregationBits); err != nil {
return nil, err
} else if c {
// If b is fully contained in a, then b can be removed.
contributions = append(contributions[:j], contributions[j+1:]...)
j--
} else if c, err := b.AggregationBits.Contains(a.AggregationBits); err != nil {
return nil, err
} else if c {
// if a is fully contained in b, then a can be removed.
contributions = append(contributions[:i], contributions[i+1:]...)
break // Stop the inner loop, advance a.
}
}
}
return contributions, nil
}
// aggregates pair of sync contributions c1 and c2 together.
func aggregate(c1, c2 *v2.SyncCommitteeContribution) (*v2.SyncCommitteeContribution, error) {
if o, err := c1.AggregationBits.Overlaps(c2.AggregationBits); err != nil {
return nil, err
} else if o {
return nil, aggregation.ErrBitsOverlap
}
baseContribution := v2.CopySyncCommitteeContribution(c1)
newContribution := v2.CopySyncCommitteeContribution(c2)
if newContribution.AggregationBits.Count() > baseContribution.AggregationBits.Count() {
baseContribution, newContribution = newContribution, baseContribution
}
if c, err := baseContribution.AggregationBits.Contains(newContribution.AggregationBits); err != nil {
return nil, err
} else if c {
return baseContribution, nil
}
newBits, err := baseContribution.AggregationBits.Or(newContribution.AggregationBits)
if err != nil {
return nil, err
}
newSig, err := dilithium.SignatureFromBytes(newContribution.Signature)
if err != nil {
return nil, err
}
baseSig, err := dilithium.SignatureFromBytes(baseContribution.Signature)
if err != nil {
return nil, err
}
aggregatedSig := dilithium.AggregateSignatures([]dilithium.Signature{baseSig, newSig})
baseContribution.Signature = aggregatedSig.Marshal()
baseContribution.AggregationBits = newBits
return baseContribution, nil
}