-
Notifications
You must be signed in to change notification settings - Fork 913
/
bad_encoding.go
252 lines (220 loc) · 7.41 KB
/
bad_encoding.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
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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
package byzantine
import (
"bytes"
"errors"
"fmt"
"github.com/celestiaorg/celestia-app/pkg/wrapper"
"github.com/celestiaorg/go-fraud"
"github.com/celestiaorg/rsmt2d"
"github.com/celestiaorg/celestia-node/header"
"github.com/celestiaorg/celestia-node/share"
pb "github.com/celestiaorg/celestia-node/share/eds/byzantine/pb"
"github.com/celestiaorg/celestia-node/share/ipld"
)
const (
version = "v0.1"
BadEncoding fraud.ProofType = "badencoding" + version
)
type BadEncodingProof struct {
headerHash []byte
BlockHeight uint64
// ShareWithProof contains all shares from row or col.
// Shares that did not pass verification in rsmt2d will be nil.
// For non-nil shares MerkleProofs are computed.
Shares []*ShareWithProof
// Index represents the row/col index where ErrByzantineRow/ErrByzantineColl occurred.
Index uint32
// Axis represents the axis that verification failed on.
Axis rsmt2d.Axis
}
// CreateBadEncodingProof creates a new Bad Encoding Fraud Proof that should be propagated through
// network. The fraud proof will contain shares that did not pass verification and their relevant
// Merkle proofs.
func CreateBadEncodingProof(
hash []byte,
height uint64,
errByzantine *ErrByzantine,
) fraud.Proof[*header.ExtendedHeader] {
return &BadEncodingProof{
headerHash: hash,
BlockHeight: height,
Shares: errByzantine.Shares,
Index: errByzantine.Index,
Axis: errByzantine.Axis,
}
}
// Type returns type of fraud proof.
func (p *BadEncodingProof) Type() fraud.ProofType {
return BadEncoding
}
// HeaderHash returns block hash.
func (p *BadEncodingProof) HeaderHash() []byte {
return p.headerHash
}
// Height returns block height.
func (p *BadEncodingProof) Height() uint64 {
return p.BlockHeight
}
// MarshalBinary converts BadEncodingProof to binary.
func (p *BadEncodingProof) MarshalBinary() ([]byte, error) {
shares := make([]*pb.Share, 0, len(p.Shares))
for _, share := range p.Shares {
shares = append(shares, share.ShareWithProofToProto())
}
badEncodingFraudProof := pb.BadEncoding{
HeaderHash: p.headerHash,
Height: p.BlockHeight,
Shares: shares,
Index: p.Index,
Axis: pb.Axis(p.Axis),
}
return badEncodingFraudProof.Marshal()
}
// UnmarshalBinary converts binary to BadEncodingProof.
func (p *BadEncodingProof) UnmarshalBinary(data []byte) error {
in := pb.BadEncoding{}
if err := in.Unmarshal(data); err != nil {
return err
}
befp := &BadEncodingProof{
headerHash: in.HeaderHash,
BlockHeight: in.Height,
Shares: ProtoToShare(in.Shares),
Index: in.Index,
Axis: rsmt2d.Axis(in.Axis),
}
*p = *befp
return nil
}
var (
errHeightMismatch = errors.New("height reported in proof does not match with the header's height")
errIncorrectIndex = errors.New("row/col index is more then the roots amount")
errIncorrectAmountOfShares = errors.New("incorrect amount of shares")
errIncorrectShare = errors.New("incorrect share received")
errNMTTreeRootsMatch = errors.New("recomputed root matches the DAH root")
)
var invalidProofPrefix = fmt.Sprintf("invalid %s proof", BadEncoding)
// Validate ensures that fraud proof is correct.
// Validate checks that provided Merkle Proofs correspond to the shares,
// rebuilds bad row or col from received shares, computes Merkle Root
// and compares it with block's Merkle Root.
func (p *BadEncodingProof) Validate(hdr *header.ExtendedHeader) error {
if hdr.Height() != p.BlockHeight {
log.Debugf("%s: %s. expected block's height: %d, got: %d",
invalidProofPrefix,
errHeightMismatch,
hdr.Height(),
p.BlockHeight,
)
return errHeightMismatch
}
if len(hdr.DAH.RowRoots) != len(hdr.DAH.ColumnRoots) {
// NOTE: This should never happen as callers of this method should not feed it with a
// malformed extended header.
panic(fmt.Sprintf(
"invalid extended header: length of row and column roots do not match. (rowRoots=%d) (colRoots=%d)",
len(hdr.DAH.RowRoots),
len(hdr.DAH.ColumnRoots)),
)
}
// merkleRoots are the roots against which we are going to check the inclusion of the received
// shares. Changing the order of the roots to prove the shares relative to the orthogonal axis,
// because inside the rsmt2d library rsmt2d.Row = 0 and rsmt2d.Col = 1
merkleRoots := hdr.DAH.RowRoots
if p.Axis == rsmt2d.Row {
merkleRoots = hdr.DAH.ColumnRoots
}
if int(p.Index) >= len(merkleRoots) {
log.Debugf("%s:%s (%d >= %d)",
invalidProofPrefix, errIncorrectIndex, int(p.Index), len(merkleRoots),
)
return errIncorrectIndex
}
if len(p.Shares) != len(merkleRoots) {
// Since p.Shares should contain all the shares from either a row or a
// column, it should exactly match the number of row roots. In this
// context, the number of row roots is the width of the extended data
// square.
log.Infof("%s: %s (%d >= %d)",
invalidProofPrefix, errIncorrectAmountOfShares, int(p.Index), len(merkleRoots),
)
return errIncorrectAmountOfShares
}
odsWidth := uint64(len(merkleRoots) / 2)
amount := uint64(0)
for _, share := range p.Shares {
if share == nil {
continue
}
amount++
if amount == odsWidth {
break
}
}
if amount < odsWidth {
log.Debugf("%s: %s. not enough shares provided to reconstruct row/col",
invalidProofPrefix, errIncorrectAmountOfShares)
return errIncorrectAmountOfShares
}
// verify that Merkle proofs correspond to particular shares.
shares := make([][]byte, len(merkleRoots))
for index, shr := range p.Shares {
if shr == nil {
continue
}
// validate inclusion of the share into one of the DAHeader roots
if ok := shr.Validate(ipld.MustCidFromNamespacedSha256(merkleRoots[index])); !ok {
log.Debugf("%s: %s at index %d", invalidProofPrefix, errIncorrectShare, index)
return errIncorrectShare
}
// NMTree commits the additional namespace while rsmt2d does not know about, so we trim it
// this is ugliness from NMTWrapper that we have to embrace ¯\_(ツ)_/¯
shares[index] = share.GetData(shr.Share)
}
codec := share.DefaultRSMT2DCodec()
// We can conclude that the proof is valid in case we proved the inclusion of `Shares` but
// the row/col can't be reconstructed, or the building of NMTree fails.
rebuiltShares, err := codec.Decode(shares)
if err != nil {
log.Debugw("failed to decode shares at height",
"height", hdr.Height(), "err", err,
)
return nil
}
rebuiltExtendedShares, err := codec.Encode(rebuiltShares[0:odsWidth])
if err != nil {
log.Debugw("failed to encode shares at height",
"height", hdr.Height(), "err", err,
)
return nil
}
copy(rebuiltShares[odsWidth:], rebuiltExtendedShares)
tree := wrapper.NewErasuredNamespacedMerkleTree(odsWidth, uint(p.Index))
for _, share := range rebuiltShares {
err = tree.Push(share)
if err != nil {
log.Debugw("failed to build a tree from the reconstructed shares at height",
"height", hdr.Height(), "err", err,
)
return nil
}
}
expectedRoot, err := tree.Root()
if err != nil {
log.Debugw("failed to build a tree root at height",
"height", hdr.Height(), "err", err,
)
return nil
}
// root is a merkle root of the row/col where ErrByzantine occurred
root := hdr.DAH.RowRoots[p.Index]
if p.Axis == rsmt2d.Col {
root = hdr.DAH.ColumnRoots[p.Index]
}
// comparing rebuilt Merkle Root of bad row/col with respective Merkle Root of row/col from block.
if bytes.Equal(expectedRoot, root) {
log.Debugf("invalid %s proof:%s", BadEncoding, errNMTTreeRootsMatch)
return errNMTTreeRootsMatch
}
return nil
}