mmrblobs

package
v0.0.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 1, 2024 License: MIT Imports: 10 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	IndexEntryBytes     = 32 * 2
	KeyBitSizeLogBase2  = 8
	KeyByteSizeLogBase2 = 5

	EventIDFirst     = 0
	EventIDEnd       = EventIDFirst + 16
	SnowflakeIdFirst = 24
	SnowflakeIdEnd   = SnowflakeIdFirst + 8
	AssetIDFirst     = SnowflakeIdEnd
	AssetIDEnd       = AssetIDFirst + 16
)
View Source 
const (
	ValueBits             = 128
	ValueBytes            = 32
	IndexHeaderBytes      = 32
	LogEntryBytes         = 32
	EntryByteSizeLogBase2 = 5
	ValueBitSizeLogBase2  = 8
	ValueByteSizeLogBase2 = 5
)
View Source 
const (
	MassifStartKeyVersionFirstByte = 21
	MassifStartKeyVersionSize      = 2 // 16 bit
	MassifStartKeyVersionEnd       = MassifStartKeyVersionFirstByte + MassifStartKeyVersionSize
	MassifStartKeyEpochFirstByte   = MassifStartKeyVersionEnd
	MassifStartKeyEpochSize        = 4 // 32 bit
	MassifStartKeyEpochEnd         = MassifStartKeyEpochFirstByte + MassifStartKeyEpochSize
	// Note the massif height is purposefully ahead of the index, it can't be
	// changed without also incrementing the EPOCH, so we never care about it's
	// effect on the  sort order with respect to the first index
	MassifStartKeyMassifHeightFirstByte = MassifStartKeyEpochEnd
	MassifStartKeyMassifHeightSize      = 1 // 8 bit
	MassifStartKeyMassifHeightEnd       = MassifStartKeyMassifHeightFirstByte + MassifStartKeyMassifHeightSize

	MassifStartKeyMassifFirstByte     = MassifStartKeyMassifHeightEnd
	MassifStartKeyMassifSize          = 4
	MassifStartKeyMassifEnd           = MassifStartKeyMassifFirstByte + MassifStartKeyMassifSize // 32 bit
	MassifStartKeyFirstIndexFirstByte = MassifStartKeyMassifEnd

	MassifCurrentVersion = uint16(0)
)
View Source 
const (
	V1MMRPrefix      = "v1/mmrs"
	V1MMRBlobNameFmt = "%016d.log"
)

Variables

View Source 
var (
	ErrLogEntryToSmall = errors.New("to few bytes to represent a valid log entry")
	ErrLogValueToSmall = errors.New("to few bytes to represent a valid log value")
	ErrLogValueBadSize = errors.New("log value size invalid")
)
View Source 
var (
	ErrGetIndexUnavailable  = errors.New("requested mmr index not available")
	ErrAncestorStackInvalid = errors.New("the ancestor stack is invalid due to bad header information")
)
View Source 
var (
	ErrMassifFixedHeaderMissing = errors.New("the fixed header for the massif is missing")
	ErrMassifFixedHeaderBadType = errors.New("the fixed header for the massif has the wrong type code")

	ErrEntryTypeUnexpected = errors.New("the entry type was not as expected")
	ErrEntryTypeInvalid    = errors.New("the entry type was invalid")
	ErrMassifBelowMinSize  = errors.New("a massive blob always has at least three log entries")
	ErrPrevRootNotSet      = errors.New("the previous root was not provided")
)
View Source 
var (
	ErrIndexEntryBadSize = errors.New("log index size invalid")
)
View Source 
var (
	ErrNotleaf = errors.New("mmr node not a leaf")
)

Functions

func BlobRead 

func BlobRead(
	ctx context.Context, blobPath string, store massifReader,
	opts ...azblob.Option) (*azblob.ReaderResponse, []byte, error)

BlobRead reads the blob of the given store.

func DecodeMassifStart 

func DecodeMassifStart(ms *MassifStart, start []byte) error

func EmptyIndexEntry 

func EmptyIndexEntry() []byte

EmptyIndexEntry is a convenience method for unit tests that don't require a valid index entry

func EncodeMassifStart 

func EncodeMassifStart(version uint16, epoch uint32, massifHeight uint8, massifIndex uint32) []byte

EncodeMassifStart encodes the massif details in the prescribed massif header record format

. | type| <reserved>| version| epoch |massif height| massif i | . | 0 | | 21 - 22 | 23 26|27 27| 28 - 31 | bytes | 1 | | 2 | 4 | 1 | 4 |

func GetIndexSnowflakeID 

func GetIndexSnowflakeID(
	data []byte, offset uint64,
) uint64

func IndexFromBlobSize 

func IndexFromBlobSize(size int) uint64

func IndexedLogValue 

func IndexedLogValue(logData []byte, i uint64) []byte

IndexedValue returns the value bytes from log data corresponding to entry index i. No range checks are performed, out of range will panic

func MassifFirstLeaf 

func MassifFirstLeaf(massifHeight uint8, massifIndex uint32) uint64

MassifFirstLeaf returns the MMR index of the first leaf in the massif blob identified by massifIndex

func MassifIndexFromLeafIndex 

func MassifIndexFromLeafIndex(massifHeight uint8, leafIndex uint64) uint64

MassifIndexFromLeafIndex gets the massif index of the massif that the given leaf is stored in, 

given the leaf index of the leaf.

This is found with the given massif height, which is constant for all massifs.

func MassifIndexFromMMRIndex 

func MassifIndexFromMMRIndex(massifHeight uint8, mmrIndex uint64) (uint64, error)

MassifIndexFromMMRIndex gets the massif index of the massif that the given leaf is stored in 

given the mmr index of the leaf.

NOTE: if the mmrIndex is not a leaf node, then error is returned.

func NewIndexEntry 

func NewIndexEntry(
	assetId uuid.UUID, eventId uuid.UUID, snowflakeId uint64,
) []byte

NewIndexEntry creates an index entry directly from the required components

func RangeLastLeafIndex 

func RangeLastLeafIndex(firstIndex uint64, height uint8) uint64

RangeLastLeafIndex returns the mmr index of the last leaf given the first index of a massif and its height.

func RangeRootIndex 

func RangeRootIndex(firstIndex uint64, height uint8) uint64

RangeRootIndex return the Massif root node's index in the overall MMR given the massif height and the first index of the MMR it contains

func SetIndexEntry 

func SetIndexEntry(
	data []byte, offset uint64,
	assetId uuid.UUID, eventId uuid.UUID, snowflakeId uint64,
)

SetIndexEntry populates the mmr blob index entry at the provided data offset

| 0 - 127 | 128 - 185| 184 - 191 | 192 - 255 | | event uuid| reserved | reserved (epoch) | snowflakeid| | 0 - 15 | 16 - 22| 23 | 24 - 31| | 16 | 7 | 1 | 8 | | asset uuid| reserved | | 256 - 384| 384 - - 512 | | 16 | 16 |

func SetIndexSnowflakeID 

func SetIndexSnowflakeID(
	data []byte, offset uint64,
	snowflakeId uint64,
)

func TenantMassifBlobPath 

func TenantMassifBlobPath(tenantIdentity string, number uint64) string

TenantEpochMountainBlobPath returns the appropriate blob path for the blob

We partition the blob space conveniently for working with the double batched merkle log accumulator scheme described by Justin Drake [here](https://ethresear.ch/t/double-batched-merkle-log-accumulator/571)

The returned string forms a relative resource name with a versioned resource prefix of 'v1/mmrs'

Because azure blob names and tags sort and compare only *lexically*, The number is represented in that path as a 16 digit hex string.

func TenantMassifPrefix 

func TenantMassifPrefix(tenantIdentity string) string

func TreeCount 

func TreeCount(height uint8) uint64

MaxCount returns the node count

func TreeLastLeafIndex 

func TreeLastLeafIndex(height uint8) uint64

TreeLastLeafIndex returns the index of the last leaf in the tree with the given height (1 << h) - h -1 works because the number of nodes required to include the last leaf is always equal to the MMR height produced by that

func TreeRootIndex 

func TreeRootIndex(height uint8) uint64

TreeRootIndex returns the root index for the tree with height

func TreeSize 

func TreeSize(height uint8) uint64

TreeSize returns the maximum byte size of the tree based on the defined log entry size

Types

type IndexHeader 

type IndexHeader struct {
	Index uint64
}

IndexHeader exists to keep track of the number of leaves represented by the mmr data.

Background:

By keeping the index and the log together, we guarantee mutual consistency - provided the log and the idex values are correctly calculated, a single write commits the change back to the blob store.

Because the data is combined, we can't use file size as a proxy for the membership count.

Regardless of whether we pre-allocate the index data or whether we accumulate it as we do the mmr, we need to know how many leaves are in the index. An algorithm to derive a leaf index form an MMR position exists, it is sub linear but a bit fiddly to get right.

At least for now, we are going to explicitly track the count of leaves in a counter value in the blob.

type KeyType 

type KeyType uint8
const (
	KeyTypeApplicationContent KeyType = iota // this is the standard entry type, purposefuly defined as 0

	KeyTypeApplicationLast // first 8 types are reserved for the application

	// KeyTypeInteriorNode trie keys for MMR interior nodes have this type
	KeyTypeInteriorNode

	// KeyTypeMassifStart is the type for keys which correspond to massif blob
	// header values
	KeyTypeMassifStart
	KeyTypeMax
)

type LogEntry 

type LogEntry struct {
	Data []byte
}

func (*LogEntry) CopyBytes 

func (le *LogEntry) CopyBytes(b []byte) int

func (LogEntry) Entry 

func (le LogEntry) Entry() []byte

func (*LogEntry) SetBytes 

func (le *LogEntry) SetBytes(b []byte) error

func (LogEntry) Value 

func (le LogEntry) Value() []byte

type MassifContext 

type MassifContext struct {
	TenantIdentity string
	BlobPath       string
	Tags           map[string]string
	ETag           string
	LastRead       time.Time
	LastModfified  time.Time

	// Read from the first log entry in the blob. If Creating is true and Found
	// > 0, this is the Start header of the *previous* massif
	Start MassifStart
	Data  []byte
	// contains filtered or unexported fields
}
1 << 3 - 1 << 2 = 8 - 4 = 4
1 << 4 - 1 << 3 = 16 - 8 = 8

Massif Root Index 7-1 | 8+7-2 | 16 + 7-2 Massif Last Leaf Index 5-1 | 8+5-2 | 16 + 5-2

In order to require the power 2 property for the leaf count, we configure the massif size by its 'height'. Here, our 4 leaf tree has height 3 (level index 2)

So typically instead of n + n -1, where n is the massif leaf count we instead do

Massif Root Index = (1 << h) - 2 Massif Last Leaf Index = (1 << h) - h - 1

func (MassifContext) Count 

func (mc MassifContext) Count() uint64

Count returns the number of log entries in the massif

func (MassifContext) FixedHeaderEnd 

func (mc MassifContext) FixedHeaderEnd() uint64

func (*MassifContext) Get 

func (mc *MassifContext) Get(i uint64) ([]byte, error)

Get returns the value associated with the node at MMR index i

Note that due to the structure of the MMR we are guaranteed that adding a node will only reference other nodes in the *current* massif, OR it will reference the root of the previous massif. As we link the massif blobs by including the root of the previous massif as the value for the first massif entry, we can return it directly. Eg in fhe following, the left child of position 15 is the root of massif 0 at position 7, and similarly, the left child of the root of massif 2 will be position 15. As Get works in indices, that will be indices 14 and 6. 

3        \   15   massif 1 \ . massif 2
          \/    \           \
 massif 0 /\     \           |
         /   \    \          |
2 ..... 7.....|....14........|...... 22 .....
      /   \   |   /   \      |      /
1    3     6  | 10     13    |    18     21
    / \  /  \ | / \    /  \  |   /  \
   1   2 4   5| 8   9 11   12| 16   17 19 20
   0   1 3   4| 7   8 10   11| 15   16 18 19
   | massif 0 |  massif 1 .  | massif 2 ....>

This method satisfies the Get method of the MMR NodeAdder interface

func (MassifContext) IndexEnd 

func (mc MassifContext) IndexEnd() uint64

IndexEnd returns the byte index of the end of index data

func (MassifContext) IndexHeaderEnd 

func (mc MassifContext) IndexHeaderEnd() uint64

IndexHeaderEhd returns the end of the bytes reserved for the index header. Currently, nothing is stored in this. XXX: TODO: Consider removing the field all together

func (MassifContext) IndexHeaderStart 

func (mc MassifContext) IndexHeaderStart() uint64

func (MassifContext) IndexLen 

func (mc MassifContext) IndexLen() uint64

func (MassifContext) IndexSize 

func (mc MassifContext) IndexSize() uint64

func (MassifContext) IndexStart 

func (mc MassifContext) IndexStart() uint64

IndexStart returns the index of the first **byte** of index data.

func (MassifContext) LogStart 

func (mc MassifContext) LogStart() uint64

func (MassifContext) PeakStackStart 

func (mc MassifContext) PeakStackStart() uint64

func (MassifContext) RangeCount 

func (mc MassifContext) RangeCount() uint64

RangeCount returns the total number of log entries in the MMR upto and including this context

type MassifReader 

type MassifReader struct {
	// contains filtered or unexported fields
}

func NewMassifReader 

func NewMassifReader(log logger.Logger, store massifReader) *MassifReader

func (*MassifReader) GetMassif 

func (mr *MassifReader) GetMassif(
	ctx context.Context, tenantIdentity string, massifIndex uint64,
	opts ...azblob.Option,
) (MassifContext, error)

type MassifStart 

type MassifStart struct {
	MassifHeight uint8
	Version      uint16
	Epoch        uint32
	MassifIndex  uint32
	FirstIndex   uint64
	PeakStackLen uint64
}

func NewMassifStart 

func NewMassifStart(epoch uint32, massifHeight uint8, massifIndex uint32, firstIndex uint64) MassifStart

func (MassifStart) MarshalBinary 

func (ms MassifStart) MarshalBinary() ([]byte, error)

func (*MassifStart) UnmarshalBinary 

func (ms *MassifStart) UnmarshalBinary(b []byte) error

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.