Go Merkle Tree. High performance, Supporting parallel run, OpenZeppelin sorting pairs.
Home Page: https://pkg.go.dev/github.com/txaty/go-merkletree
License: MIT License
I find this library sort the hashed leafs two pairs only:
func concatSortHash(b1 []byte, b2 []byte) []byte {
if bytes.Compare(b1, b2) < 0 {
return concatHash(b1, b2)
}
return concatHash(b2, b1)
}
While this library(github.com/FantasyJony/openzeppelin-merkle-tree-go) sort all the leaves and generate the same root as this js library (https://github.com/OpenZeppelin/merkle-tree)
func (st *StandardTree) MakeTree() ([]byte, error) {
if len(st.leaves) == 0 {
return nil, errors.New("Expected non-zero number of leaves")
}
// sort hash
leafValues := make([]*LeafValue, len(st.leaves))
for k, v := range st.leaves {
leafValues[k] = v
}
sort.Slice(leafValues, func(i, j int) bool {
return compareBytes(leafValues[i].Hash, leafValues[j].Hash)
})
......
}
I tried to use customer hash function as FantasyJony one by using this config:
func myHashFunc(data []byte) ([]byte, error) {
k1, err := smt.Keccak256(data)
if err != nil {
return nil, err
}
k2, err := smt.Keccak256(k1)
return k2, err
}
I think it's the sorting difference makes the different root value, am I right? (But I tried only two leaves and no sorting, still get different root value.)
If I'm wrong, could you please give me an example code to generate the same result. Thank you.
BTW: It seems your library is fast, but API is not that convenient. If there is an AddLeaf or something like to make it possible to use it in 'iteratoring or streaming style' rather than collect all the data to an array in the first place and pass to this library which allocate arrays inside to waste redundant memory.
Running a tests using the -race flag, and using this lib to generate merkle hashes throw a data race signal
Why merkle tree can't be from 1 node?
Line 104 in ccfc3d2
Even if there's just one mode, we still can compute 1 node merkle tree.
What is the standard solution?
solidity:
// SPDX-License-Identifier: MIT
pragma solidity 0.8.19;
import {MerkleProof} from "openzeppelin-contracts/utils/cryptography/MerkleProof.sol";
contract MerkleTreeUtil {
function verifyMerkle(bytes32[] memory merkleProof, bytes32 _merkleRoot, address minterAddress)
internal
pure
returns (bool)
{
return MerkleProof.verify(merkleProof, _merkleRoot, keccak256(abi.encode(minterAddress)));
}
}contract address：https://holesky.etherscan.io/address/0x2468f946031a903a1047bE72258c86d4fAA489c6#readContract
The following writing method cannot be validated on Solidity：
go:
import (
"github.com/ethereum/go-ethereum/common"
"github.com/ethereum/go-ethereum/common/hexutil"
"github.com/ethereum/go-ethereum/crypto"
"github.com/pkg/errors"
"github.com/stretchr/testify/require"
"nft-common/cryptor"
"testing"
mt "github.com/txaty/go-merkletree"
)
var leaves = []string{
"0x6EFd53BA1f3DD573EAc80B82b4B6266F6dEFA4bD",
"0x0F9C1bcC4BA8a85194ABe5B14565eB43CDEe2ed7",
"0xf852007A9Cb2771a34DAF6fc5d2AD430a638beae",
"0x2bF965771801faC320eBC067AF5aEC1a0AB62fA2",
"0x560950f740916F1c6D0750EC1b7ad2bd98691BC7",
"0x3535d10Fc0E85fDBC810bF828F02C9BcB7C2EBA8",
"0x680A72cB90322537c664Dedd5F6A1423eD892F0F",
"0xe583DC38863aB4b5A94da77A6628e2119eaD4B18",
"0x892e7c8C5E716e17891ABf9395a0de1f2fc84786",
}
func testLeafHashFunc(address common.Address) ([]byte, error) {
codeBytes, err := cryptor.AbiCoder([]string{"address"}, []interface{}{address})
if err != nil {
return nil, errors.Wrap(err, "AbiCoder")
}
hash := crypto.Keccak256Hash(codeBytes)
return hash.Bytes(), nil
}
func TestLeafHash(t *testing.T) {
for _, leaf := range leaves {
hashBytes, err := testLeafHashFunc(common.HexToAddress(leaf))
require.NoError(t, err)
t.Log(common.BytesToHash(hashBytes).Hex())
}
}
func LeafHashFunc(addressByte []byte) ([]byte, error) {
address := common.BytesToAddress(addressByte)
codeBytes, err := cryptor.AbiCoder([]string{"address"}, []interface{}{address})
if err != nil {
return nil, errors.Wrap(err, "AbiCoder")
}
hash := crypto.Keccak256Hash(codeBytes)
return hash.Bytes(), nil
}
type Leave string
func (l Leave) Serialize() ([]byte, error) {
return hexutil.Decode(string(l))
}
func TestOpenzeppelinSortMerkleTree(t *testing.T) {
config := &mt.Config{
HashFunc: LeafHashFunc,
NumRoutines: 0,
Mode: mt.ModeProofGenAndTreeBuild,
RunInParallel: false,
SortSiblingPairs: true,
DisableLeafHashing: false,
}
dataBlocks := make([]mt.DataBlock, 0, len(leaves))
for _, leaf := range leaves {
dataBlocks = append(dataBlocks, Leave(leaf))
}
merkleTree, err := mt.New(config, dataBlocks)
require.NoError(t, err)
root := hexutil.Encode(merkleTree.Root)
t.Log(root)
proofs := merkleTree.Proofs
t.Log(ProofsStrings(proofs))
node := Leave("0x6EFd53BA1f3DD573EAc80B82b4B6266F6dEFA4bD")
proof, err := merkleTree.Proof(node)
require.NoError(t, err)
t.Log(ProofStrings(proof))
verify, err := merkleTree.Verify(node, proof)
require.NoError(t, err)
require.True(t, verify)
}
func ProofStrings(p *mt.Proof) []string {
res := make([]string, 0)
for _, sibling := range p.Siblings {
proof := hexutil.Encode(sibling)
res = append(res, proof)
}
return res
}
func ProofsStrings(p []*mt.Proof) [][]string {
res := make([][]string, 0)
for _, proof := range p {
pp := make([]string, 0)
for _, sibling := range proof.Siblings {
pHex := hexutil.Encode(sibling)
pp = append(pp, pHex)
}
res = append(res, pp)
}
return res
}
Hi, you might want to consider adding go-merkletree to awesome-go, it appears to meet all their criteria. 😎
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.