diff options
Diffstat (limited to 'merkle.go')
| -rw-r--r-- | merkle.go | 75 |
1 files changed, 71 insertions, 4 deletions
@@ -1,8 +1,10 @@ package main import ( + "bytes" "encoding/binary" "os" + "sync" "golang.org/x/crypto/sha3" ) @@ -10,7 +12,7 @@ import ( var hashSize = int64(sha3.New256().Size()) type Merkle interface { - Build() []byte + Build(parallel bool) []byte Put(id int64, data []byte) Read(buf []byte, id int64) Size() int64 @@ -56,8 +58,16 @@ func (m *BFSMerkle) Read(buf []byte, id int64) { m.ReadAt(buf, id*hashSize) } +func (m *BFSMerkle) Build(parallel bool) []byte { + if parallel { + return m.parallelbuild() + } else { + return m.build() + } +} + // disk access is sequential and mostly backward -func (m *BFSMerkle) Build() []byte { +func (m *BFSMerkle) build() []byte { size := m.Size() h := sha3.New256() hsize := int64(h.Size()) @@ -82,6 +92,53 @@ func (m *BFSMerkle) Build() []byte { return buf } +func (m *BFSMerkle) parallelbuild() []byte { + size := m.Size() + hsize := hashSize + var left int64 + var wg sync.WaitGroup + p := 100 + + i := 0 + for id := size / 2; id <= size; id++ { + wg.Add(1) + go func(id int64) { + defer wg.Done() + var buf bytes.Buffer + binary.Write(&buf, binary.LittleEndian, id) + hash := sha3.Sum256(buf.Bytes()) + m.WriteAt(hash[:], id*hsize) + }(id) + if i%p == 0 { + wg.Wait() + } + i++ + } + + for height := m.height - 1; height >= 1; height-- { + left = 1 << uint64(height-1) + i := 0 + for id := left - 1; id < 2*left-1; id++ { + wg.Add(1) + go func(id int64) { + defer wg.Done() + buf := make([]byte, 2*hsize) + m.ReadAt(buf, (id*2+1)*hsize) + m.ReadAt(buf[hsize:], (id*2+2)*hsize) + hash := sha3.Sum256(buf) + m.WriteAt(hash[:], id*hsize) + }(id) + if i%p == 0 { + wg.Wait() + } + i++ + } + } + buf := make([]byte, hsize) + m.ReadAt(buf, 0) + return buf +} + func (m *BFSMerkle) Proof(id int64) [][]byte { proof := make([][]byte, m.height) proof[0] = make([]byte, hashSize) @@ -124,7 +181,9 @@ func (m *BFSMerkle) BatchProofs(ids []int64) [][][]byte { for i := range proofs { proofs[i][height] = make([]byte, hashSize) id = tids[i] - if id&1 == 0 { + if i > 0 && id == tids[i-1] { + proofs[i][height] = proofs[i-1][height] + } else if id&1 == 0 { m.ReadAt(proofs[i][height], (id-1)*hashSize) } else { m.ReadAt(proofs[i][height], (id+1)*hashSize) @@ -167,7 +226,7 @@ func (m *PostMerkle) Read(buf []byte, id int64) { // Iterative post-order depth-first construction of the Merkle tree // disk access is optimal and forward -func (m *PostMerkle) Build() []byte { +func (m *PostMerkle) Build(parallel bool) []byte { size := m.Size() h := sha3.New256() hsize := int64(h.Size()) @@ -235,3 +294,11 @@ func (m *PostMerkle) Proof(id int64) [][]byte { m.ReadAt(proof[0], cur*hashSize) return proof } + +func (m *PostMerkle) Proofs(ids []int64) [][][]byte { + proofs := make([][][]byte, len(ids)) + for i, id := range ids { + proofs[i] = m.Proof(id) + } + return proofs +} |