sharding.go

Documentation: github.com/sigstore/rekor/pkg/sharding

     1  //
     2  // Copyright 2021 The Sigstore Authors.
     3  //
     4  // Licensed under the Apache License, Version 2.0 (the "License");
     5  // you may not use this file except in compliance with the License.
     6  // You may obtain a copy of the License at
     7  //
     8  //     http://www.apache.org/licenses/LICENSE-2.0
     9  //
    10  // Unless required by applicable law or agreed to in writing, software
    11  // distributed under the License is distributed on an "AS IS" BASIS,
    12  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  // See the License for the specific language governing permissions and
    14  // limitations under the License.
    15  
    16  package sharding
    17  
    18  import (
    19  	"encoding/hex"
    20  	"errors"
    21  	"fmt"
    22  	"strconv"
    23  )
    24  
    25  // An EntryID refers to a specific artifact's ID and is made of two components,
    26  // the TreeID and the UUID. The TreeID is a hex-encoded uint64 (8 bytes)
    27  // referring to the specific trillian tree (also known as log or shard) where
    28  // the artifact can be found. The UUID is a hex-encoded 32-byte number
    29  // referring to the artifact's merkle leaf hash from trillian. Artifact lookup
    30  // by UUID occurs by finding the UUID within the tree specified by the TreeID.
    31  //
    32  // An EntryID is 40 bytes long and looks like this:
    33  // FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF
    34  // |_______  ________| |_____________________________________  ______________________________________|
    35  //         \/                                                \/
    36  // TreeID (8 bytes, hex)                             UUID (32 bytes, hex)
    37  
    38  const TreeIDHexStringLen = 16
    39  const UUIDHexStringLen = 64
    40  const EntryIDHexStringLen = TreeIDHexStringLen + UUIDHexStringLen
    41  
    42  type EntryID struct {
    43  	TreeID string
    44  	UUID   string
    45  }
    46  
    47  // CreateEntryIDFromParts This function can take a TreeID of equal or lesser length than TreeIDHexStringLen. In
    48  // case the TreeID length is less than TreeIDHexStringLen, it will be padded to the correct
    49  // length.
    50  func CreateEntryIDFromParts(treeid string, uuid string) (EntryID, error) {
    51  	if len(treeid) > TreeIDHexStringLen {
    52  		err := fmt.Errorf("invalid treeid len: %v", len(treeid))
    53  		return createEmptyEntryID(), err
    54  	}
    55  
    56  	if len(uuid) != UUIDHexStringLen {
    57  		err := fmt.Errorf("invalid uuid len: %v", len(uuid))
    58  		return createEmptyEntryID(), err
    59  	}
    60  
    61  	treeidFormatted, err := PadToTreeIDLen(treeid)
    62  	if err != nil {
    63  		return createEmptyEntryID(), err
    64  	}
    65  
    66  	if err := ValidateEntryID(treeidFormatted + uuid); err != nil {
    67  		return createEmptyEntryID(), err
    68  	}
    69  
    70  	return EntryID{
    71  		TreeID: treeidFormatted,
    72  		UUID:   uuid}, nil
    73  }
    74  
    75  func createEmptyEntryID() EntryID {
    76  	return EntryID{
    77  		TreeID: "",
    78  		UUID:   ""}
    79  }
    80  
    81  func (e EntryID) ReturnEntryIDString() string {
    82  	return e.TreeID + e.UUID
    83  }
    84  
    85  func PadToTreeIDLen(t string) (string, error) {
    86  	switch {
    87  	case len(t) == TreeIDHexStringLen:
    88  		return t, nil
    89  	case len(t) > TreeIDHexStringLen:
    90  		return "", fmt.Errorf("invalid treeID %v: too long", t)
    91  	default:
    92  		return fmt.Sprintf("%016s", t), nil
    93  	}
    94  }
    95  
    96  // GetUUIDFromIDString Returns UUID (with no prepended TreeID) from a UUID or EntryID string.
    97  // Validates UUID and also TreeID if present.
    98  func GetUUIDFromIDString(id string) (string, error) {
    99  	switch len(id) {
   100  	case UUIDHexStringLen:
   101  		if err := ValidateUUID(id); err != nil {
   102  			return "", err
   103  		}
   104  		return id, nil
   105  
   106  	case EntryIDHexStringLen:
   107  		if err := ValidateEntryID(id); err != nil {
   108  			if err.Error() == "0 is not a valid TreeID" {
   109  				return id[len(id)-UUIDHexStringLen:], nil
   110  			}
   111  			return "", err
   112  		}
   113  		return id[len(id)-UUIDHexStringLen:], nil
   114  
   115  	default:
   116  		return "", fmt.Errorf("invalid ID len %v for %v", len(id), id)
   117  	}
   118  }
   119  
   120  // ValidateUUID This is permissive in that if passed an EntryID, it will find the UUID and validate it.
   121  func ValidateUUID(u string) error {
   122  	switch len(u) {
   123  	// If u is an EntryID, call validate on just the UUID
   124  	case EntryIDHexStringLen:
   125  		uid := u[len(u)-UUIDHexStringLen:]
   126  		if err := ValidateUUID(uid); err != nil {
   127  			return err
   128  		}
   129  		return nil
   130  	case UUIDHexStringLen:
   131  		if _, err := hex.DecodeString(u); err != nil {
   132  			return fmt.Errorf("id %v is not a valid hex string: %w", u, err)
   133  		}
   134  		return nil
   135  	default:
   136  		return fmt.Errorf("invalid ID len %v for %v", len(u), u)
   137  	}
   138  }
   139  
   140  // ValidateTreeID This is permissive in that if passed an EntryID, it will find the TreeID and validate it.
   141  func ValidateTreeID(t string) error {
   142  	switch len(t) {
   143  	// If t is an EntryID, call validate on just the TreeID
   144  	case EntryIDHexStringLen:
   145  		tid := t[:TreeIDHexStringLen]
   146  		err := ValidateTreeID(tid)
   147  		if err != nil {
   148  			return err
   149  		}
   150  		return nil
   151  	case TreeIDHexStringLen:
   152  		// Check that it's a valid int64 in hex (base 16)
   153  		i, err := strconv.ParseInt(t, 16, 64)
   154  		if err != nil {
   155  			return fmt.Errorf("could not convert treeID %v to int64: %w", t, err)
   156  		}
   157  
   158  		// Check for invalid TreeID values
   159  		// TODO: test for more of these
   160  		if i == 0 {
   161  			return errors.New("0 is not a valid TreeID")
   162  		}
   163  
   164  		return nil
   165  	default:
   166  		return fmt.Errorf("TreeID len expected to be %v but got %v", TreeIDHexStringLen, len(t))
   167  	}
   168  }
   169  
   170  func ValidateEntryID(id string) error {
   171  	UUIDErr := ValidateUUID(id)
   172  	if UUIDErr != nil {
   173  		return UUIDErr
   174  	}
   175  
   176  	treeIDErr := ValidateTreeID(id)
   177  	if treeIDErr != nil {
   178  		return treeIDErr
   179  	}
   180  
   181  	return nil
   182  }
   183  
   184  var ErrPlainUUID = errors.New("cannot get treeID from plain UUID")
   185  
   186  // GetTreeIDFromIDString Returns TreeID (with no appended UUID) from a TreeID or EntryID string.
   187  // Validates TreeID and also UUID if present.
   188  func GetTreeIDFromIDString(id string) (string, error) {
   189  	switch len(id) {
   190  	case UUIDHexStringLen:
   191  		return "", ErrPlainUUID
   192  	case EntryIDHexStringLen, TreeIDHexStringLen:
   193  		if err := ValidateEntryID(id); err != nil {
   194  			return "", err
   195  		}
   196  		return id[:TreeIDHexStringLen], nil
   197  	default:
   198  		return "", fmt.Errorf("invalid ID len %v for %v", len(id), id)
   199  	}
   200  }
   201  
   202  func TreeID(entryID string) (int64, error) {
   203  	tid, err := GetTreeIDFromIDString(entryID)
   204  	if err != nil {
   205  		return 0, err
   206  	}
   207  	i, err := strconv.ParseInt(tid, 16, 64)
   208  	if err != nil {
   209  		return 0, fmt.Errorf("could not convert treeID %v to int64: %w", tid, err)
   210  	}
   211  	return i, nil
   212  }
   213
View as plain text