Add Verify in merkle tree library

Verify checks input data against the merkle tree, and compares the root
hash with expectation.

PiperOrigin-RevId: 327116711

3 files changed, 495 insertions, 84 deletions

diff --git a/pkg/merkletree/BUILD b/pkg/merkletree/BUILD
index 5b0e4143a..a8fcb2e19 100644
--- a/pkg/merkletree/BUILD
+++ b/pkg/merkletree/BUILD
@@ -5,6 +5,7 @@ package(licenses = ["notice"])
 go_library(
     name = "merkletree",
     srcs = ["merkletree.go"],
+    visibility = ["//pkg/sentry:internal"],
     deps = ["//pkg/usermem"],
 )
 
diff --git a/pkg/merkletree/merkletree.go b/pkg/merkletree/merkletree.go
index 906f67943..955c9c473 100644
--- a/pkg/merkletree/merkletree.go
+++ b/pkg/merkletree/merkletree.go
@@ -16,7 +16,9 @@
 package merkletree
 
 import (
+	"bytes"
 	"crypto/sha256"
+	"fmt"
 	"io"
 
 	"gvisor.dev/gvisor/pkg/usermem"
@@ -27,50 +29,78 @@ const (
 	sha256DigestSize = 32
 )
 
-// Size defines the scale of a Merkle tree.
-type Size struct {
+// Layout defines the scale of a Merkle tree.
+type Layout struct {
 	// blockSize is the size of a data block to be hashed.
 	blockSize int64
 	// digestSize is the size of a generated hash.
 	digestSize int64
-	// hashesPerBlock is the number of hashes in a block. For example, if
-	// blockSize is 4096 bytes, and digestSize is 32 bytes, there will be 128
-	// hashesPerBlock. Therefore 128 hashes in a lower level will be put into a
-	// block and generate a single hash in an upper level.
-	hashesPerBlock int64
-	// levelStart is the start block index of each level. The number of levels in
-	// the tree is the length of the slice. The leafs (level 0) are hashes of
-	// blocks in the input data. The levels above are hashes of lower level
-	// hashes.  The highest level is the root hash.
-	levelStart []int64
+	// levelOffset contains the offset of the begnning of each level in
+	// bytes. The number of levels in the tree is the length of the slice.
+	// The leaf nodes (level 0) contain hashes of blocks of the input data.
+	// Each level N contains hashes of the blocks in level N-1. The highest
+	// level is the root hash.
+	levelOffset []int64
 }
 
-// MakeSize initializes and returns a new Size object describing the structure
-// of a tree. dataSize specifies the number of the file system size in bytes.
-func MakeSize(dataSize int64) Size {
-	size := Size{
+// InitLayout initializes and returns a new Layout object describing the structure
+// of a tree. dataSize specifies the size of input data in bytes.
+func InitLayout(dataSize int64) Layout {
+	layout := Layout{
 		blockSize: usermem.PageSize,
 		// TODO(b/156980949): Allow config other hash methods (SHA384/SHA512).
-		digestSize:     sha256DigestSize,
-		hashesPerBlock: usermem.PageSize / sha256DigestSize,
+		digestSize: sha256DigestSize,
 	}
-	numBlocks := (dataSize + size.blockSize - 1) / size.blockSize
-	level := int64(0)
+	numBlocks := (dataSize + layout.blockSize - 1) / layout.blockSize
+	level := 0
 	offset := int64(0)
 
-	// Calcuate the number of levels in the Merkle tree and the beginning offset
-	// of each level. Level 0 is the level directly above the data blocks, while
-	// level NumLevels - 1 is the root.
+	// Calculate the number of levels in the Merkle tree and the beginning
+	// offset of each level. Level 0 consists of the leaf nodes that
+	// contain the hashes of the data blocks, while level numLevels - 1 is
+	// the root.
 	for numBlocks > 1 {
-		size.levelStart = append(size.levelStart, offset)
+		layout.levelOffset = append(layout.levelOffset, offset*layout.blockSize)
 		// Round numBlocks up to fill up a block.
-		numBlocks += (size.hashesPerBlock - numBlocks%size.hashesPerBlock) % size.hashesPerBlock
-		offset += numBlocks / size.hashesPerBlock
-		numBlocks = numBlocks / size.hashesPerBlock
+		numBlocks += (layout.hashesPerBlock() - numBlocks%layout.hashesPerBlock()) % layout.hashesPerBlock()
+		offset += numBlocks / layout.hashesPerBlock()
+		numBlocks = numBlocks / layout.hashesPerBlock()
 		level++
 	}
-	size.levelStart = append(size.levelStart, offset)
-	return size
+	layout.levelOffset = append(layout.levelOffset, offset*layout.blockSize)
+	return layout
+}
+
+// hashesPerBlock() returns the number of digests in each block.  For example,
+// if blockSize is 4096 bytes, and digestSize is 32 bytes, there will be 128
+// hashesPerBlock. Therefore 128 hashes in one level will be combined in one
+// hash in the level above.
+func (layout Layout) hashesPerBlock() int64 {
+	return layout.blockSize / layout.digestSize
+}
+
+// numLevels returns the total number of levels in the Merkle tree.
+func (layout Layout) numLevels() int {
+	return len(layout.levelOffset)
+}
+
+// rootLevel returns the level of the root hash.
+func (layout Layout) rootLevel() int {
+	return layout.numLevels() - 1
+}
+
+// digestOffset finds the offset of a digest from the beginning of the tree.
+// The target digest is at level of the tree, with index from the beginning of
+// the current level.
+func (layout Layout) digestOffset(level int, index int64) int64 {
+	return layout.levelOffset[level] + index*layout.digestSize
+}
+
+// blockOffset finds the offset of a block from the beginning of the tree.  The
+// target block is at level of the tree, with index from the beginning of the
+// current level.
+func (layout Layout) blockOffset(level int, index int64) int64 {
+	return layout.levelOffset[level] + index*layout.blockSize
 }
 
 // Generate constructs a Merkle tree for the contents of data. The output is
@@ -78,21 +108,21 @@ func MakeSize(dataSize int64) Size {
 // it has been written. That is, treeWriter and treeReader should point to the
 // same underlying data but have separate cursors.
 func Generate(data io.Reader, dataSize int64, treeReader io.Reader, treeWriter io.Writer) ([]byte, error) {
-	size := MakeSize(dataSize)
+	layout := InitLayout(dataSize)
 
-	numBlocks := (dataSize + size.blockSize - 1) / size.blockSize
+	numBlocks := (dataSize + layout.blockSize - 1) / layout.blockSize
 
 	var root []byte
-	for level := 0; level < len(size.levelStart); level++ {
+	for level := 0; level < layout.numLevels(); level++ {
 		for i := int64(0); i < numBlocks; i++ {
-			buf := make([]byte, size.blockSize)
+			buf := make([]byte, layout.blockSize)
 			var (
 				n   int
 				err error
 			)
 			if level == 0 {
-				// Read data block from the target file since level 0 is directly above
-				// the raw data block.
+				// Read data block from the target file since level 0 includes hashes
+				// of blocks in the input data.
 				n, err = data.Read(buf)
 			} else {
 				// Read data block from the tree file since levels higher than 0 are
@@ -112,7 +142,7 @@ func Generate(data io.Reader, dataSize int64, treeReader io.Reader, treeWriter i
 			// Hash the bytes in buf.
 			digest := sha256.Sum256(buf)
 
-			if level == len(size.levelStart)-1 {
+			if level == layout.rootLevel() {
 				root = digest[:]
 			}
 
@@ -121,15 +151,164 @@ func Generate(data io.Reader, dataSize int64, treeReader io.Reader, treeWriter i
 				return nil, err
 			}
 		}
-		// If the genereated digests do not round up to a block, zero-padding the
+		// If the generated digests do not round up to a block, zero-padding the
 		// remaining of the last block. But no need to do so for root.
-		if level != len(size.levelStart)-1 && numBlocks%size.hashesPerBlock != 0 {
-			zeroBuf := make([]byte, size.blockSize-(numBlocks%size.hashesPerBlock)*size.digestSize)
+		if level != layout.rootLevel() && numBlocks%layout.hashesPerBlock() != 0 {
+			zeroBuf := make([]byte, layout.blockSize-(numBlocks%layout.hashesPerBlock())*layout.digestSize)
 			if _, err := treeWriter.Write(zeroBuf[:]); err != nil {
 				return nil, err
 			}
 		}
-		numBlocks = (numBlocks + size.hashesPerBlock - 1) / size.hashesPerBlock
+		numBlocks = (numBlocks + layout.hashesPerBlock() - 1) / layout.hashesPerBlock()
 	}
 	return root, nil
 }
+
+// Verify verifies the content read from data with offset. The content is
+// verified against tree. If content spans across multiple blocks, each block is
+// verified. Verification fails if the hash of the data does not match the tree
+// at any level, or if the final root hash does not match expectedRoot.
+// Once the data is verified, it will be written using w.
+// Verify will modify the cursor for data, but always restores it to its
+// original position upon exit. The cursor for tree is modified and not
+// restored.
+func Verify(w io.Writer, data, tree io.ReadSeeker, dataSize int64, readOffset int64, readSize int64, expectedRoot []byte) error {
+	if readSize <= 0 {
+		return fmt.Errorf("Unexpected read size: %d", readSize)
+	}
+	layout := InitLayout(int64(dataSize))
+
+	// Calculate the index of blocks that includes the target range in input
+	// data.
+	firstDataBlock := readOffset / layout.blockSize
+	lastDataBlock := (readOffset + readSize - 1) / layout.blockSize
+
+	// Store the current offset, so we can set it back once verification
+	// finishes.
+	origOffset, err := data.Seek(0, io.SeekCurrent)
+	if err != nil {
+		return fmt.Errorf("Find current data offset failed: %v", err)
+	}
+	defer data.Seek(origOffset, io.SeekStart)
+
+	// Move to the first block that contains target data.
+	if _, err := data.Seek(firstDataBlock*layout.blockSize, io.SeekStart); err != nil {
+		return fmt.Errorf("Seek to datablock start failed: %v", err)
+	}
+
+	buf := make([]byte, layout.blockSize)
+	var readErr error
+	bytesRead := 0
+	for i := firstDataBlock; i <= lastDataBlock; i++ {
+		// Read a block that includes all or part of target range in
+		// input data.
+		bytesRead, readErr = data.Read(buf)
+		// If at the end of input data and all previous blocks are
+		// verified, return the verified input data and EOF.
+		if readErr == io.EOF && bytesRead == 0 {
+			break
+		}
+		if readErr != nil && readErr != io.EOF {
+			return fmt.Errorf("Read from data failed: %v", err)
+		}
+		// If this is the end of file, zero the remaining bytes in buf,
+		// otherwise they are still from the previous block.
+		// TODO(b/162908070): Investigate possible issues with zero
+		// padding the data.
+		if bytesRead < len(buf) {
+			for j := bytesRead; j < len(buf); j++ {
+				buf[j] = 0
+			}
+		}
+		if err := verifyBlock(tree, layout, buf, i, expectedRoot); err != nil {
+			return err
+		}
+		// startOff is the beginning of the read range within the
+		// current data block. Note that for all blocks other than the
+		// first, startOff should be 0.
+		startOff := int64(0)
+		if i == firstDataBlock {
+			startOff = readOffset % layout.blockSize
+		}
+		// endOff is the end of the read range within the current data
+		// block. Note that for all blocks other than the last,  endOff
+		// should be the block size.
+		endOff := layout.blockSize
+		if i == lastDataBlock {
+			endOff = (readOffset+readSize-1)%layout.blockSize + 1
+		}
+		// If the provided size exceeds the end of input data, we should
+		// only copy the parts in buf that's part of input data.
+		if startOff > int64(bytesRead) {
+			startOff = int64(bytesRead)
+		}
+		if endOff > int64(bytesRead) {
+			endOff = int64(bytesRead)
+		}
+		w.Write(buf[startOff:endOff])
+
+	}
+	return readErr
+}
+
+// verifyBlock verifies a block against tree. index is the number of block in
+// original data. The block is verified through each level of the tree. It
+// fails if the calculated hash from block is different from any level of
+// hashes stored in tree. And the final root hash is compared with
+// expectedRoot.  verifyBlock modifies the cursor for tree. Users needs to
+// maintain the cursor if intended.
+func verifyBlock(tree io.ReadSeeker, layout Layout, dataBlock []byte, blockIndex int64, expectedRoot []byte) error {
+	if len(dataBlock) != int(layout.blockSize) {
+		return fmt.Errorf("incorrect block size")
+	}
+
+	expectedDigest := make([]byte, layout.digestSize)
+	treeBlock := make([]byte, layout.blockSize)
+	var digest []byte
+	for level := 0; level < layout.numLevels(); level++ {
+		// Calculate hash.
+		if level == 0 {
+			digestArray := sha256.Sum256(dataBlock)
+			digest = digestArray[:]
+		} else {
+			// Read a block in previous level that contains the
+			// hash we just generated, and generate a next level
+			// hash from it.
+			if _, err := tree.Seek(layout.blockOffset(level-1, blockIndex), io.SeekStart); err != nil {
+				return err
+			}
+			if _, err := tree.Read(treeBlock); err != nil {
+				return err
+			}
+			digestArray := sha256.Sum256(treeBlock)
+			digest = digestArray[:]
+		}
+
+		// Move to stored hash for the current block, read the digest
+		// and store in expectedDigest.
+		if _, err := tree.Seek(layout.digestOffset(level, blockIndex), io.SeekStart); err != nil {
+			return err
+		}
+		if _, err := tree.Read(expectedDigest); err != nil {
+			return err
+		}
+
+		if !bytes.Equal(digest, expectedDigest) {
+			return fmt.Errorf("Verification failed")
+		}
+
+		// If this is the root layer, no need to generate next level
+		// hash.
+		if level == layout.rootLevel() {
+			break
+		}
+		blockIndex = blockIndex / layout.hashesPerBlock()
+	}
+
+	// Verification for the tree succeeded. Now compare the root hash in the
+	// tree with expectedRoot.
+	if !bytes.Equal(digest[:], expectedRoot) {
+		return fmt.Errorf("Verification failed")
+	}
+	return nil
+}
diff --git a/pkg/merkletree/merkletree_test.go b/pkg/merkletree/merkletree_test.go
index 7344db0b6..911f61df9 100644
--- a/pkg/merkletree/merkletree_test.go
+++ b/pkg/merkletree/merkletree_test.go
@@ -17,45 +17,48 @@ package merkletree
 import (
 	"bytes"
 	"fmt"
+	"io"
+	"math/rand"
 	"testing"
+	"time"
 
 	"gvisor.dev/gvisor/pkg/usermem"
 )
 
-func TestSize(t *testing.T) {
+func TestLayout(t *testing.T) {
 	testCases := []struct {
-		dataSize           int64
-		expectedLevelStart []int64
+		dataSize            int64
+		expectedLevelOffset []int64
 	}{
 		{
-			dataSize:           100,
-			expectedLevelStart: []int64{0},
+			dataSize:            100,
+			expectedLevelOffset: []int64{0},
 		},
 		{
-			dataSize:           1000000,
-			expectedLevelStart: []int64{0, 2, 3},
+			dataSize:            1000000,
+			expectedLevelOffset: []int64{0, 2 * usermem.PageSize, 3 * usermem.PageSize},
 		},
 		{
-			dataSize:           4096 * int64(usermem.PageSize),
-			expectedLevelStart: []int64{0, 32, 33},
+			dataSize:            4096 * int64(usermem.PageSize),
+			expectedLevelOffset: []int64{0, 32 * usermem.PageSize, 33 * usermem.PageSize},
 		},
 	}
 
 	for _, tc := range testCases {
 		t.Run(fmt.Sprintf("%d", tc.dataSize), func(t *testing.T) {
-			s := MakeSize(tc.dataSize)
-			if s.blockSize != int64(usermem.PageSize) {
-				t.Errorf("got blockSize %d, want %d", s.blockSize, usermem.PageSize)
+			p := InitLayout(tc.dataSize)
+			if p.blockSize != int64(usermem.PageSize) {
+				t.Errorf("got blockSize %d, want %d", p.blockSize, usermem.PageSize)
 			}
-			if s.digestSize != sha256DigestSize {
-				t.Errorf("got digestSize %d, want %d", s.digestSize, sha256DigestSize)
+			if p.digestSize != sha256DigestSize {
+				t.Errorf("got digestSize %d, want %d", p.digestSize, sha256DigestSize)
 			}
-			if len(s.levelStart) != len(tc.expectedLevelStart) {
-				t.Errorf("got levels %d, want %d", len(s.levelStart), len(tc.expectedLevelStart))
+			if p.numLevels() != len(tc.expectedLevelOffset) {
+				t.Errorf("got levels %d, want %d", p.numLevels(), len(tc.expectedLevelOffset))
 			}
-			for i := 0; i < len(s.levelStart) && i < len(tc.expectedLevelStart); i++ {
-				if s.levelStart[i] != tc.expectedLevelStart[i] {
-					t.Errorf("got levelStart[%d] %d, want %d", i, s.levelStart[i], tc.expectedLevelStart[i])
+			for i := 0; i < p.numLevels() && i < len(tc.expectedLevelOffset); i++ {
+				if p.levelOffset[i] != tc.expectedLevelOffset[i] {
+					t.Errorf("got levelStart[%d] %d, want %d", i, p.levelOffset[i], tc.expectedLevelOffset[i])
 				}
 			}
 		})
@@ -66,57 +69,285 @@ func TestGenerate(t *testing.T) {
 	// The input data has size dataSize. It starts with the data in startWith,
 	// and all other bytes are zeroes.
 	testCases := []struct {
-		dataSize     int
-		startWith    []byte
+		data         []byte
 		expectedRoot []byte
 	}{
 		{
-			dataSize:     usermem.PageSize,
-			startWith:    nil,
+			data:         bytes.Repeat([]byte{0}, usermem.PageSize),
 			expectedRoot: []byte{173, 127, 172, 178, 88, 111, 198, 233, 102, 192, 4, 215, 209, 209, 107, 2, 79, 88, 5, 255, 124, 180, 124, 122, 133, 218, 189, 139, 72, 137, 44, 167},
 		},
 		{
-			dataSize:     128*usermem.PageSize + 1,
-			startWith:    nil,
+			data:         bytes.Repeat([]byte{0}, 128*usermem.PageSize+1),
 			expectedRoot: []byte{62, 93, 40, 92, 161, 241, 30, 223, 202, 99, 39, 2, 132, 113, 240, 139, 117, 99, 79, 243, 54, 18, 100, 184, 141, 121, 238, 46, 149, 202, 203, 132},
 		},
 		{
-			dataSize:     1,
-			startWith:    []byte{'a'},
+			data:         []byte{'a'},
 			expectedRoot: []byte{52, 75, 204, 142, 172, 129, 37, 14, 145, 137, 103, 203, 11, 162, 209, 205, 30, 169, 213, 72, 20, 28, 243, 24, 242, 2, 92, 43, 169, 59, 110, 210},
 		},
 		{
-			dataSize:     1,
-			startWith:    []byte{'1'},
-			expectedRoot: []byte{74, 35, 103, 179, 176, 149, 254, 112, 42, 65, 104, 66, 119, 56, 133, 124, 228, 15, 65, 161, 150, 0, 117, 174, 242, 34, 115, 115, 218, 37, 3, 105},
+			data:         bytes.Repeat([]byte{'a'}, usermem.PageSize),
+			expectedRoot: []byte{201, 62, 238, 45, 13, 176, 47, 16, 172, 199, 70, 13, 149, 118, 225, 34, 220, 248, 205, 83, 196, 191, 141, 252, 174, 27, 62, 116, 235, 207, 255, 90},
 		},
 	}
 
 	for _, tc := range testCases {
-		t.Run(fmt.Sprintf("%d", tc.dataSize), func(t *testing.T) {
-			var (
-				data bytes.Buffer
-				tree bytes.Buffer
-			)
+		t.Run(fmt.Sprintf("%d:%v", len(tc.data), tc.data[0]), func(t *testing.T) {
+			var tree bytes.Buffer
 
-			startSize := len(tc.startWith)
-			_, err := data.Write(tc.startWith)
+			root, err := Generate(bytes.NewBuffer(tc.data), int64(len(tc.data)), &tree, &tree)
 			if err != nil {
-				t.Fatalf("Failed to write to data: %v", err)
+				t.Fatalf("Generate failed: %v", err)
 			}
-			_, err = data.Write(make([]byte, tc.dataSize-startSize))
-			if err != nil {
-				t.Fatalf("Failed to write to data: %v", err)
+
+			if !bytes.Equal(root, tc.expectedRoot) {
+				t.Errorf("Unexpected root")
 			}
+		})
+	}
+}
+
+// bytesReadWriter is used to read from/write to/seek in a byte array. Unlike
+// bytes.Buffer, it keeps the whole buffer during read so that it can be reused.
+type bytesReadWriter struct {
+	// bytes contains the underlying byte array.
+	bytes []byte
+	// readPos is the currently location for Read. Write always appends to
+	// the end of the array.
+	readPos int
+}
+
+func (brw *bytesReadWriter) Write(p []byte) (int, error) {
+	brw.bytes = append(brw.bytes, p...)
+	return len(p), nil
+}
+
+func (brw *bytesReadWriter) Read(p []byte) (int, error) {
+	if brw.readPos >= len(brw.bytes) {
+		return 0, io.EOF
+	}
+	bytesRead := copy(p, brw.bytes[brw.readPos:])
+	brw.readPos += bytesRead
+	if bytesRead < len(p) {
+		return bytesRead, io.EOF
+	}
+	return bytesRead, nil
+}
+
+func (brw *bytesReadWriter) Seek(offset int64, whence int) (int64, error) {
+	off := offset
+	if whence == io.SeekCurrent {
+		off += int64(brw.readPos)
+	}
+	if whence == io.SeekEnd {
+		off += int64(len(brw.bytes))
+	}
+	if off < 0 {
+		panic("seek with negative offset")
+	}
+	if off >= int64(len(brw.bytes)) {
+		return 0, io.EOF
+	}
+	brw.readPos = int(off)
+	return off, nil
+}
+
+func TestVerify(t *testing.T) {
+	// The input data has size dataSize. The portion to be verified ranges from
+	// verifyStart with verifySize. A bit is flipped in outOfRangeByteIndex to
+	// confirm that modifications outside the verification range does not cause
+	// issue. And a bit is flipped in modifyByte to confirm that
+	// modifications in the verification range is caught during verification.
+	testCases := []struct {
+		dataSize    int64
+		verifyStart int64
+		verifySize  int64
+		// A byte in input data is modified during the test. If the
+		// modified byte falls in verification range, Verify should
+		// fail, otherwise Verify should still succeed.
+		modifyByte    int64
+		shouldSucceed bool
+	}{
+		// Verify range start outside the data range should fail.
+		{
+			dataSize:      usermem.PageSize,
+			verifyStart:   usermem.PageSize,
+			verifySize:    1,
+			modifyByte:    0,
+			shouldSucceed: false,
+		},
+		// Verifying range is valid if it starts inside data and ends
+		// outside data range, in that case start to the end of data is
+		// verified.
+		{
+			dataSize:      usermem.PageSize,
+			verifyStart:   0,
+			verifySize:    2 * usermem.PageSize,
+			modifyByte:    0,
+			shouldSucceed: false,
+		},
+		// Invalid verify range (negative size) should fail.
+		{
+			dataSize:      usermem.PageSize,
+			verifyStart:   1,
+			verifySize:    -1,
+			modifyByte:    0,
+			shouldSucceed: false,
+		},
+		// Invalid verify range (0 size) should fail.
+		{
+			dataSize:      usermem.PageSize,
+			verifyStart:   0,
+			verifySize:    0,
+			modifyByte:    0,
+			shouldSucceed: false,
+		},
+		// The test cases below use a block-aligned verify range.
+		// Modifying a byte in the verified range should cause verify
+		// to fail.
+		{
+			dataSize:      8 * usermem.PageSize,
+			verifyStart:   4 * usermem.PageSize,
+			verifySize:    usermem.PageSize,
+			modifyByte:    4 * usermem.PageSize,
+			shouldSucceed: false,
+		},
+		// Modifying a byte before the verified range should not cause
+		// verify to fail.
+		{
+			dataSize:      8 * usermem.PageSize,
+			verifyStart:   4 * usermem.PageSize,
+			verifySize:    usermem.PageSize,
+			modifyByte:    4*usermem.PageSize - 1,
+			shouldSucceed: true,
+		},
+		// Modifying a byte after the verified range should not cause
+		// verify to fail.
+		{
+			dataSize:      8 * usermem.PageSize,
+			verifyStart:   4 * usermem.PageSize,
+			verifySize:    usermem.PageSize,
+			modifyByte:    5 * usermem.PageSize,
+			shouldSucceed: true,
+		},
+		// The tests below use a non-block-aligned verify range.
+		// Modifying a byte at strat of verify range should cause
+		// verify to fail.
+		{
+			dataSize:      8 * usermem.PageSize,
+			verifyStart:   4*usermem.PageSize + 123,
+			verifySize:    2 * usermem.PageSize,
+			modifyByte:    4*usermem.PageSize + 123,
+			shouldSucceed: false,
+		},
+		// Modifying a byte at the end of verify range should cause
+		// verify to fail.
+		{
+			dataSize:      8 * usermem.PageSize,
+			verifyStart:   4*usermem.PageSize + 123,
+			verifySize:    2 * usermem.PageSize,
+			modifyByte:    6*usermem.PageSize + 123,
+			shouldSucceed: false,
+		},
+		// Modifying a byte in the middle verified block should cause
+		// verify to fail.
+		{
+			dataSize:      8 * usermem.PageSize,
+			verifyStart:   4*usermem.PageSize + 123,
+			verifySize:    2 * usermem.PageSize,
+			modifyByte:    5*usermem.PageSize + 123,
+			shouldSucceed: false,
+		},
+		// Modifying a byte in the first block in the verified range
+		// should cause verify to fail, even the modified bit itself is
+		// out of verify range.
+		{
+			dataSize:      8 * usermem.PageSize,
+			verifyStart:   4*usermem.PageSize + 123,
+			verifySize:    2 * usermem.PageSize,
+			modifyByte:    4*usermem.PageSize + 122,
+			shouldSucceed: false,
+		},
+		// Modifying a byte in the last block in the verified range
+		// should cause verify to fail, even the modified bit itself is
+		// out of verify range.
+		{
+			dataSize:      8 * usermem.PageSize,
+			verifyStart:   4*usermem.PageSize + 123,
+			verifySize:    2 * usermem.PageSize,
+			modifyByte:    6*usermem.PageSize + 124,
+			shouldSucceed: false,
+		},
+	}
+
+	for _, tc := range testCases {
+		t.Run(fmt.Sprintf("%d", tc.modifyByte), func(t *testing.T) {
+			data := make([]byte, tc.dataSize)
+			// Generate random bytes in data.
+			rand.Read(data)
+			var tree bytesReadWriter
 
-			root, err := Generate(&data, int64(tc.dataSize), &tree, &tree)
+			root, err := Generate(bytes.NewBuffer(data), int64(tc.dataSize), &tree, &tree)
 			if err != nil {
 				t.Fatalf("Generate failed: %v", err)
 			}
 
-			if !bytes.Equal(root, tc.expectedRoot) {
-				t.Errorf("Unexpected root")
+			// Flip a bit in data and checks Verify results.
+			var buf bytes.Buffer
+			data[tc.modifyByte] ^= 1
+			if tc.shouldSucceed {
+				if err := Verify(&buf, bytes.NewReader(data), &tree, tc.dataSize, tc.verifyStart, tc.verifySize, root); err != nil && err != io.EOF {
+					t.Errorf("Verification failed when expected to succeed: %v", err)
+				}
+				if int64(buf.Len()) != tc.verifySize || !bytes.Equal(data[tc.verifyStart:tc.verifyStart+tc.verifySize], buf.Bytes()) {
+					t.Errorf("Incorrect output from Verify")
+				}
+			} else {
+				if err := Verify(&buf, bytes.NewReader(data), &tree, tc.dataSize, tc.verifyStart, tc.verifySize, root); err == nil {
+					t.Errorf("Verification succeeded when expected to fail")
+				}
 			}
 		})
 	}
 }
+
+func TestVerifyRandom(t *testing.T) {
+	rand.Seed(time.Now().UnixNano())
+	// Use a random dataSize.  Minimum size 2 so that we can pick a random
+	// portion from it.
+	dataSize := rand.Int63n(200*usermem.PageSize) + 2
+	data := make([]byte, dataSize)
+	// Generate random bytes in data.
+	rand.Read(data)
+	var tree bytesReadWriter
+
+	root, err := Generate(bytes.NewBuffer(data), int64(dataSize), &tree, &tree)
+	if err != nil {
+		t.Fatalf("Generate failed: %v", err)
+	}
+
+	// Pick a random portion of data.
+	start := rand.Int63n(dataSize - 1)
+	size := rand.Int63n(dataSize) + 1
+
+	var buf bytes.Buffer
+	// Checks that the random portion of data from the original data is
+	// verified successfully.
+	if err := Verify(&buf, bytes.NewReader(data), &tree, dataSize, start, size, root); err != nil && err != io.EOF {
+		t.Errorf("Verification failed for correct data: %v", err)
+	}
+	if size > dataSize-start {
+		size = dataSize - start
+	}
+	if int64(buf.Len()) != size || !bytes.Equal(data[start:start+size], buf.Bytes()) {
+		t.Errorf("Incorrect output from Verify")
+	}
+
+	buf.Reset()
+	// Flip a random bit in randPortion, and check that verification fails.
+	randBytePos := rand.Int63n(size)
+	data[start+randBytePos] ^= 1
+
+	if err := Verify(&buf, bytes.NewReader(data), &tree, dataSize, start, size, root); err == nil {
+		t.Errorf("Verification succeeded for modified data")
+	}
+}