mirror of
https://github.com/fluencelabs/tendermint
synced 2025-04-25 06:42:16 +00:00
12fa9d1cab
* crypto/merkle: Remove byter in favor of plain byte slices This PR is fully backwards compatible in terms of function output! (The Go API differs though) The only test case changes was to refactor it to be table driven. * Update godocs per review comments
95 lines
2.0 KiB
Go
95 lines
2.0 KiB
Go
package merkle
|
|
|
|
import (
|
|
"bytes"
|
|
|
|
amino "github.com/tendermint/go-amino"
|
|
"github.com/tendermint/tendermint/crypto/tmhash"
|
|
cmn "github.com/tendermint/tendermint/libs/common"
|
|
)
|
|
|
|
// Merkle tree from a map.
|
|
// Leaves are `hash(key) | hash(value)`.
|
|
// Leaves are sorted before Merkle hashing.
|
|
type simpleMap struct {
|
|
kvs cmn.KVPairs
|
|
sorted bool
|
|
}
|
|
|
|
func newSimpleMap() *simpleMap {
|
|
return &simpleMap{
|
|
kvs: nil,
|
|
sorted: false,
|
|
}
|
|
}
|
|
|
|
// Set creates a kv pair of the key and the hash of the value,
|
|
// and then appends it to simpleMap's kv pairs.
|
|
func (sm *simpleMap) Set(key string, value []byte) {
|
|
sm.sorted = false
|
|
|
|
// The value is hashed, so you can
|
|
// check for equality with a cached value (say)
|
|
// and make a determination to fetch or not.
|
|
vhash := tmhash.Sum(value)
|
|
|
|
sm.kvs = append(sm.kvs, cmn.KVPair{
|
|
Key: []byte(key),
|
|
Value: vhash,
|
|
})
|
|
}
|
|
|
|
// Hash Merkle root hash of items sorted by key
|
|
// (UNSTABLE: and by value too if duplicate key).
|
|
func (sm *simpleMap) Hash() []byte {
|
|
sm.Sort()
|
|
return hashKVPairs(sm.kvs)
|
|
}
|
|
|
|
func (sm *simpleMap) Sort() {
|
|
if sm.sorted {
|
|
return
|
|
}
|
|
sm.kvs.Sort()
|
|
sm.sorted = true
|
|
}
|
|
|
|
// Returns a copy of sorted KVPairs.
|
|
// NOTE these contain the hashed key and value.
|
|
func (sm *simpleMap) KVPairs() cmn.KVPairs {
|
|
sm.Sort()
|
|
kvs := make(cmn.KVPairs, len(sm.kvs))
|
|
copy(kvs, sm.kvs)
|
|
return kvs
|
|
}
|
|
|
|
//----------------------------------------
|
|
|
|
// A local extension to KVPair that can be hashed.
|
|
// Key and value are length prefixed and concatenated,
|
|
// then hashed.
|
|
type KVPair cmn.KVPair
|
|
|
|
// Bytes returns key || value, with both the
|
|
// key and value length prefixed.
|
|
func (kv KVPair) Bytes() []byte {
|
|
var b bytes.Buffer
|
|
err := amino.EncodeByteSlice(&b, kv.Key)
|
|
if err != nil {
|
|
panic(err)
|
|
}
|
|
err = amino.EncodeByteSlice(&b, kv.Value)
|
|
if err != nil {
|
|
panic(err)
|
|
}
|
|
return b.Bytes()
|
|
}
|
|
|
|
func hashKVPairs(kvs cmn.KVPairs) []byte {
|
|
kvsH := make([][]byte, len(kvs))
|
|
for i, kvp := range kvs {
|
|
kvsH[i] = KVPair(kvp).Bytes()
|
|
}
|
|
return SimpleHashFromByteSlices(kvsH)
|
|
}
|