.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/mod@v0.3.0/sumdb/tlog/tlog.go

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