diff options
| -rw-r--r-- | main.go | 6 | ||||
| -rw-r--r-- | merkle.go | 39 | ||||
| -rw-r--r-- | merkle_test.go | 71 |
3 files changed, 99 insertions, 17 deletions
@@ -24,9 +24,11 @@ func main() { m := NewMerkle(*mtype, *height, *fname) m.Build() /* + root := make([]byte, hashSize) + m.Read(root, 0) fmt.Println(root) - id := p.Size() / 2 - proof := p.Proof(id) + id := m.Size()/2 + 1 + proof := m.Proof(id) fmt.Println(verify(id, proof)) */ } @@ -85,7 +85,7 @@ func (m *BFSMerkle) Build() []byte { func (m *BFSMerkle) Proof(id int64) [][]byte { proof := make([][]byte, m.height) proof[0] = make([]byte, hashSize) - m.Read(proof[0], id) + m.ReadAt(proof[0], id*hashSize) for i := 1; id > 0; i++ { proof[i] = make([]byte, hashSize) if id&1 == 0 { @@ -98,6 +98,43 @@ func (m *BFSMerkle) Proof(id int64) [][]byte { return proof } +func (m *BFSMerkle) Proofs(ids []int64) [][][]byte { + proofs := make([][][]byte, len(ids)) + for i, id := range ids { + proofs[i] = m.Proof(id) + } + return proofs +} + +func (m *BFSMerkle) BatchProofs(ids []int64) [][][]byte { + proofs := make([][][]byte, len(ids)) + tids := make([]int64, len(ids)) + copy(tids, ids) + var id int64 + + // pre-allocating proofs + first step + for i := range proofs { + proofs[i] = make([][]byte, m.height) + proofs[i][0] = make([]byte, hashSize) + m.ReadAt(proofs[i][0], tids[i]*hashSize) + } + + // constructing proofs level by level + for height := int64(1); height < m.height; height++ { + for i := range proofs { + proofs[i][height] = make([]byte, hashSize) + id = tids[i] + if id&1 == 0 { + m.ReadAt(proofs[i][height], (id-1)*hashSize) + } else { + m.ReadAt(proofs[i][height], (id+1)*hashSize) + } + tids[i] = (id - 1) >> 1 + } + } + return proofs +} + // nodes are stored in depth-first post order type PostMerkle struct { height int64 diff --git a/merkle_test.go b/merkle_test.go index f3a070e..adc8861 100644 --- a/merkle_test.go +++ b/merkle_test.go @@ -4,9 +4,14 @@ import ( "bytes" "fmt" "math/rand" + "os" + "sort" "testing" + "time" ) +const N = 200000 + func testMerkle(mtype string) bool { m := NewMerkle(mtype, 5, "test.db") root := m.Build() @@ -36,32 +41,70 @@ func TestMerkle(t *testing.T) { } } -func BenchmarkBFSMerkle(b *testing.B) { +func TestBenchmarkBFSMerkle(t *testing.T) { m := NewBFSMerkle(25, "/mnt/data/bfs.db") - root := make([]byte, hashSize) - m.Read(root, 0) - var id int64 var proof [][]byte - for i := 0; i < b.N; i++ { - id = rand.Int63n(m.Size()/2) + m.Size()/2 - proof = m.Proof(id) + start := time.Now() + for i := 0; i < N; i++ { + proof = m.Proof(ids[i]) if len(proof) != int(m.height) { fmt.Println("error") } } + elapsed := time.Since(start) + fmt.Println(elapsed, elapsed.Nanoseconds()/N) } -func BenchmarkPostMerkle(b *testing.B) { +func TestBenchmarkPostMerkle(t *testing.T) { m := NewPostMerkle(25, "/mnt/data/post.db") - root := make([]byte, hashSize) - m.Read(root, 0) - var id int64 var proof [][]byte - for i := 0; i < b.N; i++ { - id = rand.Int63n(m.Size()/2) + m.Size()/2 - proof = m.Proof(id) + start := time.Now() + for i := 0; i < N; i++ { + proof = m.Proof(ids[i]) if len(proof) != int(m.height) { fmt.Println("error") } } + elapsed := time.Since(start) + fmt.Println(elapsed, elapsed.Nanoseconds()/N) +} + +var proofs [][][]byte + +func TestProofsBFSMerkle(t *testing.T) { + m := NewBFSMerkle(25, "/mnt/data/bfs.db") + root := make([]byte, hashSize) + m.Read(root, 0) + start := time.Now() + proofs = m.Proofs(ids) + elapsed := time.Since(start) + fmt.Println(elapsed, elapsed.Nanoseconds()/N) +} + +func TestBatchProofsBFSMerkle(t *testing.T) { + m := NewBFSMerkle(25, "/mnt/data/bfs.db") + root := make([]byte, hashSize) + m.Read(root, 0) + start := time.Now() + proofs = m.BatchProofs(ids) + elapsed := time.Since(start) + fmt.Println(elapsed, elapsed.Nanoseconds()/N) +} + +var ids []int64 + +type Int64Slice []int64 + +func (p Int64Slice) Len() int { return len(p) } +func (p Int64Slice) Less(i, j int) bool { return p[i] < p[j] } +func (p Int64Slice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } + +func TestMain(m *testing.M) { + ids = make([]int64, N) + tmp := NewBFSMerkle(25, "/mnt/data/bfs.db") + for i := 0; i < N; i++ { + ids[i] = rand.Int63n(tmp.Size()/2) + tmp.Size()/2 + } + sort.Sort(Int64Slice(ids)) + os.Exit(m.Run()) } |