-
Notifications
You must be signed in to change notification settings - Fork 16
/
stxo.go
348 lines (311 loc) · 13 KB
/
stxo.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
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
package utxo
import (
"encoding/binary"
"fmt"
"github.com/Qitmeer/qng/common/hash"
"github.com/Qitmeer/qng/consensus/model"
"github.com/Qitmeer/qng/core/dbnamespace"
"github.com/Qitmeer/qng/core/serialization"
"github.com/Qitmeer/qng/core/types"
"github.com/Qitmeer/qng/database"
)
var byteOrder = binary.LittleEndian
// The bytes of TxIndex
const SpentTxOutTxIndexSize = 4
// The bytes of TxInIndex
const SpentTxOutTxInIndexSize = 4
// The bytes of Fees field
const SpentTxoutFeesCoinIDSize = 2
const SpentTxOutFeesValueSize = 8
// The bytes of Amount's CoinId
const SpentTxoutAmountCoinIDSize = 2
// -----------------------------------------------------------------------------
// The transaction spend journal consists of an entry for each block connected
// to the main chain which contains the transaction outputs the block spends
// serialized such that the order is the reverse of the order they were spent.
//
// This is required because reorganizing the chain necessarily entails
// disconnecting blocks to get back to the point of the fork which implies
// unspending all of the transaction outputs that each block previously spent.
// Since the utxo set, by definition, only contains unspent transaction outputs,
// the spent transaction outputs must be resurrected from somewhere. There is
// more than one way this could be done, however this is the most straight
// forward method that does not require having a transaction index and unpruned
// blockchain.
//
// NOTE: This format is NOT self describing. The additional details such as
// the number of entries (transaction inputs) are expected to come from the
// block itself and the utxo set. The rationale in doing this is to save a
// significant amount of space. This is also the reason the spent outputs are
// serialized in the reverse order they are spent because later transactions
// are allowed to spend outputs from earlier ones in the same block.
//
// The serialized format is:
//
// [<flags><script version><compressed pk script>],...
// OPTIONAL: [<txVersion>]
//
// Field Type Size
// flags VLQ byte
// scriptVersion uint16 2 bytes
// pkScript VLQ+[]byte variable
//
// OPTIONAL
// txVersion VLQ variable
// stakeExtra []byte variable
//
// The serialized flags code format is:
// bit 0 - containing transaction is a coinbase
// bit 1 - containing transaction has an expiry
// bits 2-3 - transaction type
// bit 4 - is fully spent
//
// The stake extra field contains minimally encoded outputs for all
// consensus-related outputs in the stake transaction. It is only
// encoded for tickets.
//
// NOTE: The transaction version and flags are only encoded when the spent
// txout was the final unspent output of the containing transaction.
// Otherwise, the header code will be 0 and the version is not serialized at
// all. This is done because that information is only needed when the utxo
// set no longer has it.
//
// Example:
// TODO
// -----------------------------------------------------------------------------
// SpentTxOut contains a spent transaction output and potentially additional
// contextual information such as whether or not it was contained in a coinbase
// transaction, the txVersion of the transaction it was contained in, and which
// block height the containing transaction was included in. As described in
// the comments above, the additional contextual information will only be valid
// when this spent txout is spending the last unspent output of the containing
// transaction.
//
// The struct is aligned for memory efficiency.
type SpentTxOut struct {
Amount types.Amount // The total amount of the output.
PkScript []byte // The public key script for the output.
BlockHash hash.Hash
IsCoinBase bool // Whether creating tx is a coinbase.
TxIndex uint32 // The index of tx in block.
TxInIndex uint32 // The index of TxInput in the tx.
Fees types.Amount // The fees of block
}
func spentTxOutHeaderCode(stxo *SpentTxOut) uint64 {
// As described in the serialization format comments, the header code
// encodes the height shifted over one bit and the coinbase flag in the
// lowest bit.
headerCode := uint64(0)
if stxo.IsCoinBase {
headerCode |= 0x01
}
return headerCode
}
// SpentTxOutSerializeSize returns the number of bytes it would take to
// serialize the passed stxo according to the format described above.
// The amount is never encoded into spent transaction outputs because
// they're already encoded into the transactions, so skip them when
// determining the serialization size.
func spentTxOutSerializeSize(stxo *SpentTxOut) int {
size := serialization.SerializeSizeVLQ(spentTxOutHeaderCode(stxo))
size += hash.HashSize
size += SpentTxOutTxIndexSize + SpentTxOutTxInIndexSize
size += SpentTxoutFeesCoinIDSize + SpentTxOutFeesValueSize
size += SpentTxoutAmountCoinIDSize
return size + compressedTxOutSize(uint64(stxo.Amount.Value), stxo.PkScript)
}
// putSpentTxOut serializes the passed stxo according to the format described
// above directly into the passed target byte slice. The target byte slice must
// be at least large enough to handle the number of bytes returned by the
// SpentTxOutSerializeSize function or it will panic.
func putSpentTxOut(target []byte, stxo *SpentTxOut) int {
headerCode := spentTxOutHeaderCode(stxo)
offset := serialization.PutVLQ(target, headerCode)
copy(target[offset:], stxo.BlockHash.Bytes())
offset += hash.HashSize
byteOrder.PutUint32(target[offset:], uint32(stxo.TxIndex))
offset += SpentTxOutTxIndexSize
byteOrder.PutUint32(target[offset:], uint32(stxo.TxInIndex))
offset += SpentTxOutTxInIndexSize
// add Fees coinId
byteOrder.PutUint16(target[offset:], uint16(stxo.Fees.Id))
offset += SpentTxoutFeesCoinIDSize
// add Fees Value
byteOrder.PutUint64(target[offset:], uint64(stxo.Fees.Value))
offset += SpentTxOutFeesValueSize
// add Amount coinId
byteOrder.PutUint16(target[offset:], uint16(stxo.Amount.Id))
offset += SpentTxoutAmountCoinIDSize
return offset + putCompressedTxOut(target[offset:], uint64(stxo.Amount.Value), stxo.PkScript)
}
// decodeSpentTxOut decodes the passed serialized stxo entry, possibly followed
// by other data, into the passed stxo struct. It returns the number of bytes
// read.
//
// Since the serialized stxo entry does not contain the height, version, or
// coinbase flag of the containing transaction when it still has utxos, the
// caller is responsible for passing in the containing transaction version in
// that case. The provided version is ignore when it is serialized as a part of
// the stxo.
//
// An error will be returned if the version is not serialized as a part of the
// stxo and is also not provided to the function.
func decodeSpentTxOut(serialized []byte, stxo *SpentTxOut) (int, error) {
// Ensure there are bytes to decode.
if len(serialized) == 0 {
return 0, model.ErrDeserialize("no serialized bytes")
}
// Deserialize the header code.
code, offset := serialization.DeserializeVLQ(serialized)
if offset >= len(serialized) {
return offset, model.ErrDeserialize("unexpected end of data after " +
"header code")
}
// Decode the header code.
//
// Bit 0 indicates containing transaction is a coinbase.
// Bits 1-x encode height of containing transaction.
stxo.IsCoinBase = code&0x01 != 0
stxo.BlockHash.SetBytes(serialized[offset : offset+hash.HashSize])
offset += hash.HashSize
stxo.TxIndex = byteOrder.Uint32(serialized[offset : offset+SpentTxOutTxIndexSize])
offset += SpentTxOutTxIndexSize
stxo.TxInIndex = byteOrder.Uint32(serialized[offset : offset+SpentTxOutTxInIndexSize])
offset += SpentTxOutTxInIndexSize
// Decode Fees
feesCoinId := byteOrder.Uint16(serialized[offset : offset+SpentTxoutFeesCoinIDSize])
offset += SpentTxoutFeesCoinIDSize
feesValue := byteOrder.Uint64(serialized[offset : offset+SpentTxOutFeesValueSize])
offset += SpentTxOutFeesValueSize
stxo.Fees = types.Amount{Value: int64(feesValue), Id: types.CoinID(feesCoinId)}
// Decode amount coinId
amountCoinId := byteOrder.Uint16(serialized[offset : offset+SpentTxoutAmountCoinIDSize])
offset += SpentTxoutAmountCoinIDSize
// Decode the compressed txout.
amount, pkScript, bytesRead, err := decodeCompressedTxOut(
serialized[offset:])
offset += bytesRead
if err != nil {
return offset, model.ErrDeserialize(fmt.Sprintf("unable to decode "+
"txout: %v", err))
}
stxo.Amount = types.Amount{Value: int64(amount), Id: types.CoinID(amountCoinId)}
stxo.PkScript = pkScript
return offset, nil
}
// deserializeSpendJournalEntry decodes the passed serialized byte slice into a
// slice of spent txouts according to the format described in detail above.
//
// Since the serialization format is not self describing, as noted in the
// format comments, this function also requires the transactions that spend the
// txouts and a utxo view that contains any remaining existing utxos in the
// transactions referenced by the inputs to the passed transasctions.
func deserializeSpendJournalEntry(serialized []byte, txns []*types.Transaction) ([]SpentTxOut, error) {
// When a block has no spent txouts there is nothing to serialize.
if len(serialized) == 0 {
return nil, nil
}
numStxos := int(byteOrder.Uint32(serialized[0:4]))
// Loop backwards through all transactions so everything is read in
// reverse order to match the serialization order.
offset := 4
stxos := make([]SpentTxOut, numStxos)
for stxoIdx := numStxos - 1; stxoIdx > -1; stxoIdx-- {
stxo := &stxos[stxoIdx]
n, err := decodeSpentTxOut(serialized[offset:], stxo)
offset += n
if err != nil {
return nil, model.ErrDeserialize(fmt.Sprintf("unable "+
"to decode stxo for %v: %v",
stxoIdx, err))
}
}
return stxos, nil
}
// serializeSpendJournalEntry serializes all of the passed spent txouts into a
// single byte slice according to the format described in detail above.
func serializeSpendJournalEntry(stxos []SpentTxOut) ([]byte, error) {
if len(stxos) == 0 {
return nil, nil
}
// Calculate the size needed to serialize the entire journal entry.
var size int = 4
var sizes []int
for i := range stxos {
sz := spentTxOutSerializeSize(&stxos[i])
sizes = append(sizes, sz)
size += sz
}
serialized := make([]byte, size)
// Serialize each individual stxo directly into the slice in reverse
// order one after the other.
var offset int
byteOrder.PutUint32(serialized[offset:], uint32(len(stxos)))
offset += 4
for i := len(stxos) - 1; i > -1; i-- {
oldOffset := offset
offset += putSpentTxOut(serialized[offset:], &stxos[i])
if offset-oldOffset != sizes[i] {
return nil, model.AssertError(fmt.Sprintf("bad write; expect sz %v, "+
"got sz %v (wrote %x)", sizes[i], offset-oldOffset,
serialized[oldOffset:offset]))
}
}
return serialized, nil
}
// dbFetchSpendJournalEntry fetches the spend journal entry for the passed
// block and deserializes it into a slice of spent txout entries. The provided
// view MUST have the utxos referenced by all of the transactions available for
// the passed block since that information is required to reconstruct the spent
// txouts.
func DBFetchSpendJournalEntry(dbTx database.Tx, block *types.SerializedBlock) ([]SpentTxOut, error) {
// Exclude the coinbase transaction since it can't spend anything.
spendBucket := dbTx.Metadata().Bucket(dbnamespace.SpendJournalBucketName)
serialized := spendBucket.Get(block.Hash()[:])
blockTxns := block.Block().Transactions[1:]
stxos, err := deserializeSpendJournalEntry(serialized, blockTxns)
if err != nil {
// Ensure any deserialization errors are returned as database
// corruption errors.
if model.IsDeserializeErr(err) {
return nil, database.Error{
ErrorCode: database.ErrCorruption,
Description: fmt.Sprintf("corrupt spend "+
"information for %v: %v", block.Hash(),
err),
}
}
return nil, err
}
return stxos, nil
}
// dbPutSpendJournalEntry uses an existing database transaction to update the
// spend journal entry for the given block hash using the provided slice of
// spent txouts. The spent txouts slice must contain an entry for every txout
// the transactions in the block spend in the order they are spent.
func DBPutSpendJournalEntry(dbTx database.Tx, blockHash *hash.Hash, stxos []SpentTxOut) error {
if len(stxos) == 0 {
return nil
}
spendBucket := dbTx.Metadata().Bucket(dbnamespace.SpendJournalBucketName)
serialized, err := serializeSpendJournalEntry(stxos)
if err != nil {
return err
}
return spendBucket.Put(blockHash[:], serialized)
}
// dbRemoveSpendJournalEntry uses an existing database transaction to remove the
// spend journal entry for the passed block hash.
func DBRemoveSpendJournalEntry(dbTx database.Tx, blockHash *hash.Hash) error {
spendBucket := dbTx.Metadata().Bucket(dbnamespace.SpendJournalBucketName)
return spendBucket.Delete(blockHash[:])
}
func GetStxo(txIndex uint32, txInIndex uint32, stxos []SpentTxOut) *SpentTxOut {
for _, stxo := range stxos {
if stxo.TxIndex == txIndex &&
stxo.TxInIndex == txInIndex {
return &stxo
}
}
return nil
}