tlog.go

Documentation: cmd/vendor/golang.org/x/mod/sumdb/tlog

     1  // Copyright 2019 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package tlog implements a tamper-evident log
     6  // used in the Go module go.sum database server.
     7  //
     8  // This package follows the design of Certificate Transparency (RFC 6962)
     9  // and its proofs are compatible with that system.
    10  // See TestCertificateTransparency.
    11  package tlog
    12  
    13  import (
    14  	"crypto/sha256"
    15  	"encoding/base64"
    16  	"errors"
    17  	"fmt"
    18  	"math/bits"
    19  )
    20  
    21  // A Hash is a hash identifying a log record or tree root.
    22  type Hash [HashSize]byte
    23  
    24  // HashSize is the size of a Hash in bytes.
    25  const HashSize = 32
    26  
    27  // String returns a base64 representation of the hash for printing.
    28  func (h Hash) String() string {
    29  	return base64.StdEncoding.EncodeToString(h[:])
    30  }
    31  
    32  // MarshalJSON marshals the hash as a JSON string containing the base64-encoded hash.
    33  func (h Hash) MarshalJSON() ([]byte, error) {
    34  	return []byte(`"` + h.String() + `"`), nil
    35  }
    36  
    37  // UnmarshalJSON unmarshals a hash from JSON string containing the a base64-encoded hash.
    38  func (h *Hash) UnmarshalJSON(data []byte) error {
    39  	if len(data) != 1+44+1 || data[0] != '"' || data[len(data)-2] != '=' || data[len(data)-1] != '"' {
    40  		return errors.New("cannot decode hash")
    41  	}
    42  
    43  	// As of Go 1.12, base64.StdEncoding.Decode insists on
    44  	// slicing into target[33:] even when it only writes 32 bytes.
    45  	// Since we already checked that the hash ends in = above,
    46  	// we can use base64.RawStdEncoding with the = removed;
    47  	// RawStdEncoding does not exhibit the same bug.
    48  	// We decode into a temporary to avoid writing anything to *h
    49  	// unless the entire input is well-formed.
    50  	var tmp Hash
    51  	n, err := base64.RawStdEncoding.Decode(tmp[:], data[1:len(data)-2])
    52  	if err != nil || n != HashSize {
    53  		return errors.New("cannot decode hash")
    54  	}
    55  	*h = tmp
    56  	return nil
    57  }
    58  
    59  // ParseHash parses the base64-encoded string form of a hash.
    60  func ParseHash(s string) (Hash, error) {
    61  	data, err := base64.StdEncoding.DecodeString(s)
    62  	if err != nil || len(data) != HashSize {
    63  		return Hash{}, fmt.Errorf("malformed hash")
    64  	}
    65  	var h Hash
    66  	copy(h[:], data)
    67  	return h, nil
    68  }
    69  
    70  // maxpow2 returns k, the maximum power of 2 smaller than n,
    71  // as well as l = log₂ k (so k = 1<<l).
    72  func maxpow2(n int64) (k int64, l int) {
    73  	l = 0
    74  	for 1<<uint(l+1) < n {
    75  		l++
    76  	}
    77  	return 1 << uint(l), l
    78  }
    79  
    80  var zeroPrefix = []byte{0x00}
    81  
    82  // RecordHash returns the content hash for the given record data.
    83  func RecordHash(data []byte) Hash {
    84  	// SHA256(0x00 || data)
    85  	// https://tools.ietf.org/html/rfc6962#section-2.1
    86  	h := sha256.New()
    87  	h.Write(zeroPrefix)
    88  	h.Write(data)
    89  	var h1 Hash
    90  	h.Sum(h1[:0])
    91  	return h1
    92  }
    93  
    94  // NodeHash returns the hash for an interior tree node with the given left and right hashes.
    95  func NodeHash(left, right Hash) Hash {
    96  	// SHA256(0x01 || left || right)
    97  	// https://tools.ietf.org/html/rfc6962#section-2.1
    98  	// We use a stack buffer to assemble the hash input
    99  	// to avoid allocating a hash struct with sha256.New.
   100  	var buf [1 + HashSize + HashSize]byte
   101  	buf[0] = 0x01
   102  	copy(buf[1:], left[:])
   103  	copy(buf[1+HashSize:], right[:])
   104  	return sha256.Sum256(buf[:])
   105  }
   106  
   107  // For information about the stored hash index ordering,
   108  // see section 3.3 of Crosby and Wallach's paper
   109  // "Efficient Data Structures for Tamper-Evident Logging".
   110  // https://www.usenix.org/legacy/event/sec09/tech/full_papers/crosby.pdf
   111  
   112  // StoredHashIndex maps the tree coordinates (level, n)
   113  // to a dense linear ordering that can be used for hash storage.
   114  // Hash storage implementations that store hashes in sequential
   115  // storage can use this function to compute where to read or write
   116  // a given hash.
   117  func StoredHashIndex(level int, n int64) int64 {
   118  	// Level L's n'th hash is written right after level L+1's 2n+1'th hash.
   119  	// Work our way down to the level 0 ordering.
   120  	// We'll add back the original level count at the end.
   121  	for l := level; l > 0; l-- {
   122  		n = 2*n + 1
   123  	}
   124  
   125  	// Level 0's n'th hash is written at n+n/2+n/4+... (eventually n/2ⁱ hits zero).
   126  	i := int64(0)
   127  	for ; n > 0; n >>= 1 {
   128  		i += n
   129  	}
   130  
   131  	return i + int64(level)
   132  }
   133  
   134  // SplitStoredHashIndex is the inverse of [StoredHashIndex].
   135  // That is, SplitStoredHashIndex(StoredHashIndex(level, n)) == level, n.
   136  func SplitStoredHashIndex(index int64) (level int, n int64) {
   137  	// Determine level 0 record before index.
   138  	// StoredHashIndex(0, n) < 2*n,
   139  	// so the n we want is in [index/2, index/2+log₂(index)].
   140  	n = index / 2
   141  	indexN := StoredHashIndex(0, n)
   142  	if indexN > index {
   143  		panic("bad math")
   144  	}
   145  	for {
   146  		// Each new record n adds 1 + trailingZeros(n) hashes.
   147  		x := indexN + 1 + int64(bits.TrailingZeros64(uint64(n+1)))
   148  		if x > index {
   149  			break
   150  		}
   151  		n++
   152  		indexN = x
   153  	}
   154  	// The hash we want was committed with record n,
   155  	// meaning it is one of (0, n), (1, n/2), (2, n/4), ...
   156  	level = int(index - indexN)
   157  	return level, n >> uint(level)
   158  }
   159  
   160  // StoredHashCount returns the number of stored hashes
   161  // that are expected for a tree with n records.
   162  func StoredHashCount(n int64) int64 {
   163  	if n == 0 {
   164  		return 0
   165  	}
   166  	// The tree will have the hashes up to the last leaf hash.
   167  	numHash := StoredHashIndex(0, n-1) + 1
   168  	// And it will have any hashes for subtrees completed by that leaf.
   169  	for i := uint64(n - 1); i&1 != 0; i >>= 1 {
   170  		numHash++
   171  	}
   172  	return numHash
   173  }
   174  
   175  // StoredHashes returns the hashes that must be stored when writing
   176  // record n with the given data. The hashes should be stored starting
   177  // at StoredHashIndex(0, n). The result will have at most 1 + log₂ n hashes,
   178  // but it will average just under two per call for a sequence of calls for n=1..k.
   179  //
   180  // StoredHashes may read up to log n earlier hashes from r
   181  // in order to compute hashes for completed subtrees.
   182  func StoredHashes(n int64, data []byte, r HashReader) ([]Hash, error) {
   183  	return StoredHashesForRecordHash(n, RecordHash(data), r)
   184  }
   185  
   186  // StoredHashesForRecordHash is like [StoredHashes] but takes
   187  // as its second argument RecordHash(data) instead of data itself.
   188  func StoredHashesForRecordHash(n int64, h Hash, r HashReader) ([]Hash, error) {
   189  	// Start with the record hash.
   190  	hashes := []Hash{h}
   191  
   192  	// Build list of indexes needed for hashes for completed subtrees.
   193  	// Each trailing 1 bit in the binary representation of n completes a subtree
   194  	// and consumes a hash from an adjacent subtree.
   195  	m := int(bits.TrailingZeros64(uint64(n + 1)))
   196  	indexes := make([]int64, m)
   197  	for i := 0; i < m; i++ {
   198  		// We arrange indexes in sorted order.
   199  		// Note that n>>i is always odd.
   200  		indexes[m-1-i] = StoredHashIndex(i, n>>uint(i)-1)
   201  	}
   202  
   203  	// Fetch hashes.
   204  	old, err := r.ReadHashes(indexes)
   205  	if err != nil {
   206  		return nil, err
   207  	}
   208  	if len(old) != len(indexes) {
   209  		return nil, fmt.Errorf("tlog: ReadHashes(%d indexes) = %d hashes", len(indexes), len(old))
   210  	}
   211  
   212  	// Build new hashes.
   213  	for i := 0; i < m; i++ {
   214  		h = NodeHash(old[m-1-i], h)
   215  		hashes = append(hashes, h)
   216  	}
   217  	return hashes, nil
   218  }
   219  
   220  // A HashReader can read hashes for nodes in the log's tree structure.
   221  type HashReader interface {
   222  	// ReadHashes returns the hashes with the given stored hash indexes
   223  	// (see StoredHashIndex and SplitStoredHashIndex).
   224  	// ReadHashes must return a slice of hashes the same length as indexes,
   225  	// or else it must return a non-nil error.
   226  	// ReadHashes may run faster if indexes is sorted in increasing order.
   227  	ReadHashes(indexes []int64) ([]Hash, error)
   228  }
   229  
   230  // A HashReaderFunc is a function implementing [HashReader].
   231  type HashReaderFunc func([]int64) ([]Hash, error)
   232  
   233  func (f HashReaderFunc) ReadHashes(indexes []int64) ([]Hash, error) {
   234  	return f(indexes)
   235  }
   236  
   237  // TreeHash computes the hash for the root of the tree with n records,
   238  // using the HashReader to obtain previously stored hashes
   239  // (those returned by StoredHashes during the writes of those n records).
   240  // TreeHash makes a single call to ReadHash requesting at most 1 + log₂ n hashes.
   241  // The tree of size zero is defined to have an all-zero Hash.
   242  func TreeHash(n int64, r HashReader) (Hash, error) {
   243  	if n == 0 {
   244  		return Hash{}, nil
   245  	}
   246  	indexes := subTreeIndex(0, n, nil)
   247  	hashes, err := r.ReadHashes(indexes)
   248  	if err != nil {
   249  		return Hash{}, err
   250  	}
   251  	if len(hashes) != len(indexes) {
   252  		return Hash{}, fmt.Errorf("tlog: ReadHashes(%d indexes) = %d hashes", len(indexes), len(hashes))
   253  	}
   254  	hash, hashes := subTreeHash(0, n, hashes)
   255  	if len(hashes) != 0 {
   256  		panic("tlog: bad index math in TreeHash")
   257  	}
   258  	return hash, nil
   259  }
   260  
   261  // subTreeIndex returns the storage indexes needed to compute
   262  // the hash for the subtree containing records [lo, hi),
   263  // appending them to need and returning the result.
   264  // See https://tools.ietf.org/html/rfc6962#section-2.1
   265  func subTreeIndex(lo, hi int64, need []int64) []int64 {
   266  	// See subTreeHash below for commentary.
   267  	for lo < hi {
   268  		k, level := maxpow2(hi - lo + 1)
   269  		if lo&(k-1) != 0 {
   270  			panic("tlog: bad math in subTreeIndex")
   271  		}
   272  		need = append(need, StoredHashIndex(level, lo>>uint(level)))
   273  		lo += k
   274  	}
   275  	return need
   276  }
   277  
   278  // subTreeHash computes the hash for the subtree containing records [lo, hi),
   279  // assuming that hashes are the hashes corresponding to the indexes
   280  // returned by subTreeIndex(lo, hi).
   281  // It returns any leftover hashes.
   282  func subTreeHash(lo, hi int64, hashes []Hash) (Hash, []Hash) {
   283  	// Repeatedly partition the tree into a left side with 2^level nodes,
   284  	// for as large a level as possible, and a right side with the fringe.
   285  	// The left hash is stored directly and can be read from storage.
   286  	// The right side needs further computation.
   287  	numTree := 0
   288  	for lo < hi {
   289  		k, _ := maxpow2(hi - lo + 1)
   290  		if lo&(k-1) != 0 || lo >= hi {
   291  			panic("tlog: bad math in subTreeHash")
   292  		}
   293  		numTree++
   294  		lo += k
   295  	}
   296  
   297  	if len(hashes) < numTree {
   298  		panic("tlog: bad index math in subTreeHash")
   299  	}
   300  
   301  	// Reconstruct hash.
   302  	h := hashes[numTree-1]
   303  	for i := numTree - 2; i >= 0; i-- {
   304  		h = NodeHash(hashes[i], h)
   305  	}
   306  	return h, hashes[numTree:]
   307  }
   308  
   309  // A RecordProof is a verifiable proof that a particular log root contains a particular record.
   310  // RFC 6962 calls this a “Merkle audit path.”
   311  type RecordProof []Hash
   312  
   313  // ProveRecord returns the proof that the tree of size t contains the record with index n.
   314  func ProveRecord(t, n int64, r HashReader) (RecordProof, error) {
   315  	if t < 0 || n < 0 || n >= t {
   316  		return nil, fmt.Errorf("tlog: invalid inputs in ProveRecord")
   317  	}
   318  	indexes := leafProofIndex(0, t, n, nil)
   319  	if len(indexes) == 0 {
   320  		return RecordProof{}, nil
   321  	}
   322  	hashes, err := r.ReadHashes(indexes)
   323  	if err != nil {
   324  		return nil, err
   325  	}
   326  	if len(hashes) != len(indexes) {
   327  		return nil, fmt.Errorf("tlog: ReadHashes(%d indexes) = %d hashes", len(indexes), len(hashes))
   328  	}
   329  
   330  	p, hashes := leafProof(0, t, n, hashes)
   331  	if len(hashes) != 0 {
   332  		panic("tlog: bad index math in ProveRecord")
   333  	}
   334  	return p, nil
   335  }
   336  
   337  // leafProofIndex builds the list of indexes needed to construct the proof
   338  // that leaf n is contained in the subtree with leaves [lo, hi).
   339  // It appends those indexes to need and returns the result.
   340  // See https://tools.ietf.org/html/rfc6962#section-2.1.1
   341  func leafProofIndex(lo, hi, n int64, need []int64) []int64 {
   342  	// See leafProof below for commentary.
   343  	if !(lo <= n && n < hi) {
   344  		panic("tlog: bad math in leafProofIndex")
   345  	}
   346  	if lo+1 == hi {
   347  		return need
   348  	}
   349  	if k, _ := maxpow2(hi - lo); n < lo+k {
   350  		need = leafProofIndex(lo, lo+k, n, need)
   351  		need = subTreeIndex(lo+k, hi, need)
   352  	} else {
   353  		need = subTreeIndex(lo, lo+k, need)
   354  		need = leafProofIndex(lo+k, hi, n, need)
   355  	}
   356  	return need
   357  }
   358  
   359  // leafProof constructs the proof that leaf n is contained in the subtree with leaves [lo, hi).
   360  // It returns any leftover hashes as well.
   361  // See https://tools.ietf.org/html/rfc6962#section-2.1.1
   362  func leafProof(lo, hi, n int64, hashes []Hash) (RecordProof, []Hash) {
   363  	// We must have lo <= n < hi or else the code here has a bug.
   364  	if !(lo <= n && n < hi) {
   365  		panic("tlog: bad math in leafProof")
   366  	}
   367  
   368  	if lo+1 == hi { // n == lo
   369  		// Reached the leaf node.
   370  		// The verifier knows what the leaf hash is, so we don't need to send it.
   371  		return RecordProof{}, hashes
   372  	}
   373  
   374  	// Walk down the tree toward n.
   375  	// Record the hash of the path not taken (needed for verifying the proof).
   376  	var p RecordProof
   377  	var th Hash
   378  	if k, _ := maxpow2(hi - lo); n < lo+k {
   379  		// n is on left side
   380  		p, hashes = leafProof(lo, lo+k, n, hashes)
   381  		th, hashes = subTreeHash(lo+k, hi, hashes)
   382  	} else {
   383  		// n is on right side
   384  		th, hashes = subTreeHash(lo, lo+k, hashes)
   385  		p, hashes = leafProof(lo+k, hi, n, hashes)
   386  	}
   387  	return append(p, th), hashes
   388  }
   389  
   390  var errProofFailed = errors.New("invalid transparency proof")
   391  
   392  // CheckRecord verifies that p is a valid proof that the tree of size t
   393  // with hash th has an n'th record with hash h.
   394  func CheckRecord(p RecordProof, t int64, th Hash, n int64, h Hash) error {
   395  	if t < 0 || n < 0 || n >= t {
   396  		return fmt.Errorf("tlog: invalid inputs in CheckRecord")
   397  	}
   398  	th2, err := runRecordProof(p, 0, t, n, h)
   399  	if err != nil {
   400  		return err
   401  	}
   402  	if th2 == th {
   403  		return nil
   404  	}
   405  	return errProofFailed
   406  }
   407  
   408  // runRecordProof runs the proof p that leaf n is contained in the subtree with leaves [lo, hi).
   409  // Running the proof means constructing and returning the implied hash of that
   410  // subtree.
   411  func runRecordProof(p RecordProof, lo, hi, n int64, leafHash Hash) (Hash, error) {
   412  	// We must have lo <= n < hi or else the code here has a bug.
   413  	if !(lo <= n && n < hi) {
   414  		panic("tlog: bad math in runRecordProof")
   415  	}
   416  
   417  	if lo+1 == hi { // m == lo
   418  		// Reached the leaf node.
   419  		// The proof must not have any unnecessary hashes.
   420  		if len(p) != 0 {
   421  			return Hash{}, errProofFailed
   422  		}
   423  		return leafHash, nil
   424  	}
   425  
   426  	if len(p) == 0 {
   427  		return Hash{}, errProofFailed
   428  	}
   429  
   430  	k, _ := maxpow2(hi - lo)
   431  	if n < lo+k {
   432  		th, err := runRecordProof(p[:len(p)-1], lo, lo+k, n, leafHash)
   433  		if err != nil {
   434  			return Hash{}, err
   435  		}
   436  		return NodeHash(th, p[len(p)-1]), nil
   437  	} else {
   438  		th, err := runRecordProof(p[:len(p)-1], lo+k, hi, n, leafHash)
   439  		if err != nil {
   440  			return Hash{}, err
   441  		}
   442  		return NodeHash(p[len(p)-1], th), nil
   443  	}
   444  }
   445  
   446  // A TreeProof is a verifiable proof that a particular log tree contains
   447  // as a prefix all records present in an earlier tree.
   448  // RFC 6962 calls this a “Merkle consistency proof.”
   449  type TreeProof []Hash
   450  
   451  // ProveTree returns the proof that the tree of size t contains
   452  // as a prefix all the records from the tree of smaller size n.
   453  func ProveTree(t, n int64, h HashReader) (TreeProof, error) {
   454  	if t < 1 || n < 1 || n > t {
   455  		return nil, fmt.Errorf("tlog: invalid inputs in ProveTree")
   456  	}
   457  	indexes := treeProofIndex(0, t, n, nil)
   458  	if len(indexes) == 0 {
   459  		return TreeProof{}, nil
   460  	}
   461  	hashes, err := h.ReadHashes(indexes)
   462  	if err != nil {
   463  		return nil, err
   464  	}
   465  	if len(hashes) != len(indexes) {
   466  		return nil, fmt.Errorf("tlog: ReadHashes(%d indexes) = %d hashes", len(indexes), len(hashes))
   467  	}
   468  
   469  	p, hashes := treeProof(0, t, n, hashes)
   470  	if len(hashes) != 0 {
   471  		panic("tlog: bad index math in ProveTree")
   472  	}
   473  	return p, nil
   474  }
   475  
   476  // treeProofIndex builds the list of indexes needed to construct
   477  // the sub-proof related to the subtree containing records [lo, hi).
   478  // See https://tools.ietf.org/html/rfc6962#section-2.1.2.
   479  func treeProofIndex(lo, hi, n int64, need []int64) []int64 {
   480  	// See treeProof below for commentary.
   481  	if !(lo < n && n <= hi) {
   482  		panic("tlog: bad math in treeProofIndex")
   483  	}
   484  
   485  	if n == hi {
   486  		if lo == 0 {
   487  			return need
   488  		}
   489  		return subTreeIndex(lo, hi, need)
   490  	}
   491  
   492  	if k, _ := maxpow2(hi - lo); n <= lo+k {
   493  		need = treeProofIndex(lo, lo+k, n, need)
   494  		need = subTreeIndex(lo+k, hi, need)
   495  	} else {
   496  		need = subTreeIndex(lo, lo+k, need)
   497  		need = treeProofIndex(lo+k, hi, n, need)
   498  	}
   499  	return need
   500  }
   501  
   502  // treeProof constructs the sub-proof related to the subtree containing records [lo, hi).
   503  // It returns any leftover hashes as well.
   504  // See https://tools.ietf.org/html/rfc6962#section-2.1.2.
   505  func treeProof(lo, hi, n int64, hashes []Hash) (TreeProof, []Hash) {
   506  	// We must have lo < n <= hi or else the code here has a bug.
   507  	if !(lo < n && n <= hi) {
   508  		panic("tlog: bad math in treeProof")
   509  	}
   510  
   511  	// Reached common ground.
   512  	if n == hi {
   513  		if lo == 0 {
   514  			// This subtree corresponds exactly to the old tree.
   515  			// The verifier knows that hash, so we don't need to send it.
   516  			return TreeProof{}, hashes
   517  		}
   518  		th, hashes := subTreeHash(lo, hi, hashes)
   519  		return TreeProof{th}, hashes
   520  	}
   521  
   522  	// Interior node for the proof.
   523  	// Decide whether to walk down the left or right side.
   524  	var p TreeProof
   525  	var th Hash
   526  	if k, _ := maxpow2(hi - lo); n <= lo+k {
   527  		// m is on left side
   528  		p, hashes = treeProof(lo, lo+k, n, hashes)
   529  		th, hashes = subTreeHash(lo+k, hi, hashes)
   530  	} else {
   531  		// m is on right side
   532  		th, hashes = subTreeHash(lo, lo+k, hashes)
   533  		p, hashes = treeProof(lo+k, hi, n, hashes)
   534  	}
   535  	return append(p, th), hashes
   536  }
   537  
   538  // CheckTree verifies that p is a valid proof that the tree of size t with hash th
   539  // contains as a prefix the tree of size n with hash h.
   540  func CheckTree(p TreeProof, t int64, th Hash, n int64, h Hash) error {
   541  	if t < 1 || n < 1 || n > t {
   542  		return fmt.Errorf("tlog: invalid inputs in CheckTree")
   543  	}
   544  	h2, th2, err := runTreeProof(p, 0, t, n, h)
   545  	if err != nil {
   546  		return err
   547  	}
   548  	if th2 == th && h2 == h {
   549  		return nil
   550  	}
   551  	return errProofFailed
   552  }
   553  
   554  // runTreeProof runs the sub-proof p related to the subtree containing records [lo, hi),
   555  // where old is the hash of the old tree with n records.
   556  // Running the proof means constructing and returning the implied hashes of that
   557  // subtree in both the old and new tree.
   558  func runTreeProof(p TreeProof, lo, hi, n int64, old Hash) (Hash, Hash, error) {
   559  	// We must have lo < n <= hi or else the code here has a bug.
   560  	if !(lo < n && n <= hi) {
   561  		panic("tlog: bad math in runTreeProof")
   562  	}
   563  
   564  	// Reached common ground.
   565  	if n == hi {
   566  		if lo == 0 {
   567  			if len(p) != 0 {
   568  				return Hash{}, Hash{}, errProofFailed
   569  			}
   570  			return old, old, nil
   571  		}
   572  		if len(p) != 1 {
   573  			return Hash{}, Hash{}, errProofFailed
   574  		}
   575  		return p[0], p[0], nil
   576  	}
   577  
   578  	if len(p) == 0 {
   579  		return Hash{}, Hash{}, errProofFailed
   580  	}
   581  
   582  	// Interior node for the proof.
   583  	k, _ := maxpow2(hi - lo)
   584  	if n <= lo+k {
   585  		oh, th, err := runTreeProof(p[:len(p)-1], lo, lo+k, n, old)
   586  		if err != nil {
   587  			return Hash{}, Hash{}, err
   588  		}
   589  		return oh, NodeHash(th, p[len(p)-1]), nil
   590  	} else {
   591  		oh, th, err := runTreeProof(p[:len(p)-1], lo+k, hi, n, old)
   592  		if err != nil {
   593  			return Hash{}, Hash{}, err
   594  		}
   595  		return NodeHash(p[len(p)-1], oh), NodeHash(p[len(p)-1], th), nil
   596  	}
   597  }
   598
View as plain text