diff options
| -rw-r--r-- | main.go | 13 | ||||
| -rw-r--r-- | merkle.go | 50 |
2 files changed, 23 insertions, 40 deletions
@@ -2,7 +2,6 @@ package main import ( "flag" - "fmt" "log" "os" "runtime/pprof" @@ -32,9 +31,11 @@ func main() { defer pprof.StopCPUProfile() p := NewProver(*height, *fname, *mtype) - root := p.Build() - fmt.Println(root) - id := p.Size() / 2 - proof := p.Proof(id) - fmt.Println(verify(id, proof)) + p.Build() + /* + fmt.Println(root) + id := p.Size() / 2 + proof := p.Proof(id) + fmt.Println(verify(id, proof)) + */ } @@ -27,30 +27,6 @@ func NewMerkle(mtype string, height int64, fname string) Merkle { } return m } -func ChildrenId(m Merkle, id int64) (id1, id2 int64) { - id2 = (id + 1) * 2 - id1 = id2 - 1 - return id1, id2 -} - -func Children(child1, child2 []byte, id int64, m Merkle) { - id1, id2 := ChildrenId(m, id) - m.Read(child1, id1) - m.Read(child2, id2) -} - -func Init(m Merkle) { - h := sha3.New256() - hsize := h.Size() - buf := make([]byte, hsize) - - for id := m.Size() / 2; id <= m.Size(); id++ { - h.Reset() - binary.Write(h, binary.LittleEndian, id) - buf = h.Sum(buf[:0]) - m.Put(id, buf) - } -} // nodes are stored in BFS order, root node first type BFSMerkle struct { @@ -82,20 +58,26 @@ func (m *BFSMerkle) Read(buf []byte, id int64) { // disk access is sequential and mostly backward func (m *BFSMerkle) Build() []byte { - Init(m) size := m.Size() h := sha3.New256() - hsize := h.Size() - child1 := make([]byte, hsize) - child2 := make([]byte, hsize) + hsize := int64(h.Size()) buf := make([]byte, hsize) + + for id := m.Size() / 2; id <= m.Size(); id++ { + h.Reset() + binary.Write(h, binary.LittleEndian, id) + buf = h.Sum(buf[:0]) + m.WriteAt(buf, id*hsize) + } + for id := size/2 - 1; id >= 0; id-- { - Children(child1, child2, id, m) h.Reset() - h.Write(child1) - h.Write(child2) + m.ReadAt(buf, (id*2+1)*hsize) + h.Write(buf) + m.ReadAt(buf, (id*2+2)*hsize) + h.Write(buf) buf = h.Sum(buf[:0]) - m.Put(id, buf) + m.WriteAt(buf, id*hsize) } return buf } @@ -107,9 +89,9 @@ func (m *BFSMerkle) Proof(id int64) [][]byte { for i := 1; id > 0; i++ { proof[i] = make([]byte, hashSize) if id&1 == 0 { - m.Read(proof[i], id-1) + m.ReadAt(proof[i], (id-1)*hashSize) } else { - m.Read(proof[i], id+1) + m.ReadAt(proof[i], (id+1)*hashSize) } id = (id - 1) >> 1 } |