From 27ff4c4aa4988c65caf6093b9dcc3c00f6c00743 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Wed, 4 May 2016 23:10:15 -0400
Subject: Add batch proof extraction: sorting helps more than batching, will
 have to investigate page faults

---
 main.go        |  6 +++--
 merkle.go      | 39 +++++++++++++++++++++++++++++++-
 merkle_test.go | 71 ++++++++++++++++++++++++++++++++++++++++++++++------------
 3 files changed, 99 insertions(+), 17 deletions(-)

diff --git a/main.go b/main.go
index 2058437..3bf3f6b 100644
--- a/main.go
+++ b/main.go
@@ -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))
 	*/
 }
diff --git a/merkle.go b/merkle.go
index 1ef55ce..9257c64 100644
--- a/merkle.go
+++ b/merkle.go
@@ -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())
 }
-- 
cgit v1.2.3-70-g09d2