xlNodeID_go
The NodeID library for the xlattice_go project.
NodeID
A NodeID is a slice of bytes used to uniquely identify an entity. The length of the slice must be either 20 or 32 bytes.
The first is the length of an SHA1 hash and so can be used, for example, to store the SHA1 hash of a document.
SHA1, also known as SHA-1, is the Secure Hash Algorithm designed by the US National Security Agency. It is a Federal Information Processing Standard published by the National Institute of Science and Technology, FIPS180-4 /
In recent years many attempts have been made is crack SHA1, that is, to identify two documents whose SHA1 hash is the same. At this time no such hash collision has been found. Nevertheless SHA1 has been declared obsolete (ie, cryptographically insecure) and so there has been a general shift towards more secure variants of the hash, one of which is SHA-256, which produces a 256-bit/32-byte hash. For simplicity XLattice documents generally refer to this as SHA2.
Over the last several yerasa competition was held to settle on a new and still more secure hash algorithm, SHA3. The competition was won by Keccak.
SHA3 is available in a number of variants. We use Keccak-256, the 32-byte/256-bit variant. When XLattice documents refer to SHA3, we mean Keccak-256.
At this time SHA3 is not quite stabilized and so XLattice prefers SHA256 as its 32-byte hash. In other words, 32-byte XLattice NodeIDs are typically SHA2 hashes.
IDMaps
Because NodeIDs are used to uniquely identify objects within the XLattice universe, it is convenient to have utilities which can store and rapidly retrieve NodeIDs and pointers to the associated objects.
An IDMap is a trie structure which stores keys and pointers to their associated values. A key is a byte slice and assumed to be a NodeID. The value pointed to can be anything at all.
Each IDMap has a maximum depth. This is the length of the longest key can can be stored in the IDMap. By default the depth is 32, the length of an SHA2 or SHA3 hash.
When a new key is inserted into an IDMap, the software searches down the
existing tree. At each level there is a 256-cell Map. If at level N the
cell indexed by byte N is free, the new key is entered into the Map at
that level. If the cell is occupied by a key which differs in the next
byte, a new IDMap is created, with the new key and the existing key in their
respecitive cells. If the keys have equal next bytes, insertion recurses
down the tree, until a difference is found or the maximum depth is reached.
Despite the use of coarse locks, IDMap Insert and Find operations compare favorbly with that found using the HAMT algorighm as implemented in hamt_go.
Project Status
Stable and well-tested.
Licensing
The material on this github.io website is licensed under a Creative Commons Attribution 4.0 International License.
Project software is licensed under an MIT license. Follow the SOFTWARE LICENSE link below for more information on project software licensing.
