Hashing

Package bchutil provides bitcoin cash-specific convenience functions and types. A Block defines a bitcoin cash block that provides easier and more efficient manipulation of raw wire protocol blocks. It also memoizes hashes for the block and its transactions on their first access so subsequent accesses don't have to repeat the relatively expensive hashing operations. A Tx defines a bitcoin cash transaction that provides more efficient manipulation of raw wire protocol transactions. It memoizes the hash for the transaction on its first access so subsequent accesses don't have to repeat the relatively expensive hashing operations. The Address interface provides an abstraction for a Bitcoin Cashaddress. While the most common type is a pay-to-pubkey-hash, Bitcoin Cash already supports others and may well support more in the future. This package currently provides implementations for the pay-to-pubkey, pay-to-pubkey-hash, and pay-to-script-hash address types. To decode/encode an address:

Package dht implements a distributed hash table that satisfies the ipfs routing interface. This DHT is modeled after kademlia with S/Kademlia modifications.

Package btcutil provides bitcoin-specific convenience functions and types. A Block defines a bitcoin block that provides easier and more efficient manipulation of raw wire protocol blocks. It also memoizes hashes for the block and its transactions on their first access so subsequent accesses don't have to repeat the relatively expensive hashing operations. A Tx defines a bitcoin transaction that provides more efficient manipulation of raw wire protocol transactions. It memoizes the hash for the transaction on its first access so subsequent accesses don't have to repeat the relatively expensive hashing operations. The Address interface provides an abstraction for a Bitcoin address. While the most common type is a pay-to-pubkey-hash, Bitcoin already supports others and may well support more in the future. This package currently provides implementations for the pay-to-pubkey, pay-to-pubkey-hash, and pay-to-script-hash address types. To decode/encode an address:

Package amt provides a reference implementation of the IPLD AMT (Array Mapped Trie) used in the Filecoin blockchain. The AMT algorithm is similar to a HAMT https://en.wikipedia.org/wiki/Hash_array_mapped_trie but instead presents an array-like interface where the indexes themselves form the mapping to nodes in the trie structure. An AMT is suitable for storing sparse array data as a minimum amount of intermediate nodes are required to address a small number of entries even when their indexes span a large distance. AMT is also a suitable means of storing non-sparse array data as required, with a small amount of storage and algorithmic overhead required to handle mapping that assumes that some elements within any range of data may not be present. The AMT algorithm produces a tree-like graph, with a single root node addressing a collection of child nodes which connect downward toward leaf nodes which store the actual entries. No terminal entries are stored in intermediate elements of the tree, unlike in a HAMT. We can divide up the AMT tree structure into "levels" or "heights", where a height of zero contains the terminal elements, and the maximum height of the tree contains the single root node. Intermediate nodes are used to span across the range of indexes. Any AMT instance uses a fixed "width" that is consistent across the tree's nodes. An AMT's "bitWidth" dictates the width, or maximum-brancing factor (arity) of the AMT's nodes by determining how many bits of the original index are used to determine the index at any given level. A bitWidth of 3 (the default for this implementation) can generate indexes in the range of 0 to (3^2)-1=7, i.e. a "width" of 8. In practice, this means that an AMT with a bitWidth of 3 has a branching factor of _between 1 and 8_ for any node in the structure. Considering the minimal case: a minimal AMT contains a single node which serves as both the root and the leaf node and can hold zero or more elements (an empty AMT is possible, although a special-case, and consists of a zero-length root). This minimal AMT can store array indexes from 0 to width-1 (8 for the default bitWidth of 3) without requiring the addition of additional nodes. Attempts to add additional indexes beyond width-1 will result in additional nodes being added and a tree structure in order to address the new elements. The minimal AMT node is said to have a height of 0. Every node in an AMT has a height that indicates its distance from the leaf nodes. All leaf nodes have a height of 0. The height of the root node dictates the overall height of the entire AMT. In the case of the minimal AMT, this is 0. Elements are stored in a compacted form within nodes, they are "position-mapped" by a bitmap field that is stored with the node. The bitmap is a simple byte array, where each bit represents an element of the data that can be stored in the node. With a width of 8, the bitmap is a single byte and up to 8 elements can be stored in the node. The data array of a node _only stores elements that are present in that node_, so the array is commonly shorter than the maximum width. An empty AMT is a special-case where the single node can have zero elements, therefore a zero-length data array and a bitmap of `0x00`. In all other cases, the data array must have between 1 and width elements. Determining the position of an index within the data array requires counting the number of set bits within the bitmap up to the element we are concerned with. If the bitmap has bits 2, 4 and 6 set, we can see that only 3 of the bits are set so our data array should hold 3 elements. To address index 4, we know that the first element will be index 2 and therefore the second will hold index 4. This format allows us to store only the elements that are set in the node. Overflow beyond the single node AMT by adding an index beyond width-1 requires an increase in height in order to address all elements. If an element in the range of width to (width*2)-1 is added, a single additional height is required which will result in a new root node which is used to address two consecutive leaf nodes. Because we have an arity of up to width at any node, the addition of indexes in the range of 0 to (width^2)-1 will still require only the addition of a single additional height above the leaf nodes, i.e. height 1. From the width of an AMT we can derive the maximum range of indexes that can be contained by an AMT at any given `height` with the formula width^(height+1)-1. e.g. an AMT with a width of 8 and a height of 2 can address indexes 0 to 8^(2+1)-1=511. Incrementing the height doubles the range of indexes that can be contained within that structure. Nodes above height 0 (non-leaf nodes) do not contain terminal elements, but instead, their data array contains links to child nodes. The index compaction using the bitmap is the same as for leaf nodes, so each non-leaf node only stores as many links as it has child nodes. Because additional height is required to address larger indexes, even a single-element AMT will require more than one node where the index is greater than the width of the AMT. For a width of 8, indexes 8 to 63 require a height of 1, indexes 64 to 511 require a height of 2, indexes 512 to 4095 require a height of 3, etc. Retrieving elements from the AMT requires extracting only the portion of the requested index that is required at each height to determine the position in the data array to navigate into. When traversing through the tree, we only need to select from indexes 0 to width-1. To do this, we take log2(width) bits from the index to form a number that is between 0 and width-1. e.g. for a width of 8, we only need 3 bits to form a number between 0 and 7, so we only consume 3 bits per level of the AMT as we traverse. A simple method to calculate this at any height in the AMT (assuming bitWidth of 3, i.e. a width of 8) is: 1. Calculate the maximum number of nodes (not entries) that may be present in an sub-tree rooted at the current height. width^height provides this number. e.g. at height 0, only 1 node can be present, but at height 3, we may have a tree of up to 512 nodes (storing up to 8^(3+1)=4096 entries). 2. Divide the index by this number to find the index for this height. e.g. an index of 3 at height 0 will be 3/1=3, or an index of 20 at height 1 will be 20/8=2. 3. If we are at height 0, the element we want is at the data index, position-mapped via the bitmap. 4. If we are above height 0, we need to navigate to the child element at the index we calculated, position-mapped via the bitmap. When traversing to the child, we discard the upper portion of the index that we no longer need. This can be achieved by a mod operation against the number-of-nodes value. e.g. an index of 20 at height 1 requires navigation to the element at position 2, when moving to that element (which is height 0), we truncate the index with 20%8=4, at height 0 this index will be the index in our data array (position-mapped via the bitmap). In this way, each sub-tree root consumes a small slice, log2(width) bits long, of the original index. Adding new elements to an AMT may require up to 3 steps: 1. Increasing the height to accommodate a new index if the current height is not sufficient to address the new index. Increasing the height requires turning the current root node into an intermediate and adding a new root which links to the old (repeated until the required height is reached). 2. Adding any missing intermediate and leaf nodes that are required to address the new index. Depending on the density of existing indexes, this may require the addition of up to height-1 new nodes to connect the root to the required leaf. Sparse indexes will mean large gaps in the tree that will need filling to address new, equally sparse, indexes. 3. Setting the element at the leaf node in the appropriate position in the data array and setting the appropriate bit in the bitmap. Removing elements requires a reversal of this process. Any empty node (other than the case of a completely empty AMT) must be removed and its parent should have its child link removed. This removal may recurse up the tree to remove many unnecessary intermediate nodes. The root node may also be removed if the current height is no longer necessary to contain the range of indexes still in the AMT. This can be easily determined if _only_ the first bit of the root's bitmap is set, meaning only the left-most is present, which will become the new root node (repeated until the new root has more than the first bit set or height of 0, the single-node case). See https://github.com/ipld/specs/blob/master/data-structures/hashmap.md for a description of a HAMT algorithm. And https://github.com/ipld/specs/blob/master/data-structures/vector.md for a description of a similar algorithm to an AMT that doesn't support internal node compression and therefore doesn't support sparse arrays. Unlike a HAMT, the AMT algorithm doesn't benefit from randomness introduced by a hash algorithm. Therefore an AMT used in cases where user-input can influence indexes, larger-than-necessary tree structures may present risks as well as the challenge imposed by having a strict upper-limit on the indexes addressable by the AMT. A width of 8, using 64-bit integers for indexing, allows for a tree height of up to 64/log2(8)=21 (i.e. a width of 8 has a bitWidth of 3, dividing the 64 bits of the uint into 21 separate per-height indexes). Careful placement of indexes could create extremely sub-optimal forms with large heights connecting leaf nodes that are sparsely packed. The overhead of the large number of intermediate nodes required to connect leaf nodes in AMTs that contain high indexes can be abused to create perverse forms that contain large numbers of nodes to store a minimal number of elements. Minimal nodes will be created where indexes are all in the lower-range. The optimal case for an AMT is contiguous index values starting from zero. As larger indexes are introduced that span beyond the current maximum, more nodes are required to address the new nodes _and_ the existing lower index nodes. Consider a case where a width=8 AMT is only addressing indexes less than 8 and requiring a single height. The introduction of a single index within 8 of the maximum 64-bit unsigned integer range will require the new root to have a height of 21 and have enough connecting nodes between it and both the existing elements and the new upper index. This pattern of behavior may be acceptable if there is significant density of entries under a particular maximum index. There is a direct relationship between the sparseness of index values and the number of nodes required to address the entries. This should be the key consideration when determining whether an AMT is a suitable data-structure for a given application.

Package amt provides a reference implementation of the IPLD AMT (Array Mapped Trie) used in the Filecoin blockchain. The AMT algorithm is similar to a HAMT https://en.wikipedia.org/wiki/Hash_array_mapped_trie but instead presents an array-like interface where the indexes themselves form the mapping to nodes in the trie structure. An AMT is suitable for storing sparse array data as a minimum amount of intermediate nodes are required to address a small number of entries even when their indexes span a large distance. AMT is also a suitable means of storing non-sparse array data as required, with a small amount of storage and algorithmic overhead required to handle mapping that assumes that some elements within any range of data may not be present. The AMT algorithm produces a tree-like graph, with a single root node addressing a collection of child nodes which connect downward toward leaf nodes which store the actual entries. No terminal entries are stored in intermediate elements of the tree, unlike in a HAMT. We can divide up the AMT tree structure into "levels" or "heights", where a height of zero contains the terminal elements, and the maximum height of the tree contains the single root node. Intermediate nodes are used to span across the range of indexes. Any AMT instance uses a fixed "width" that is consistent across the tree's nodes. An AMT's "bitWidth" dictates the width, or maximum-brancing factor (arity) of the AMT's nodes by determining how many bits of the original index are used to determine the index at any given level. A bitWidth of 3 (the default for this implementation) can generate indexes in the range of 0 to (2^3)-1=7, i.e. a "width" of 8. In practice, this means that an AMT with a bitWidth of 3 has a branching factor of _between 1 and 8_ for any node in the structure. Considering the minimal case: a minimal AMT contains a single node which serves as both the root and the leaf node and can hold zero or more elements (an empty AMT is possible, although a special-case, and consists of a zero-length root). This minimal AMT can store array indexes from 0 to width-1 (8 for the default bitWidth of 3) without requiring the addition of additional nodes. Attempts to add additional indexes beyond width-1 will result in additional nodes being added and a tree structure in order to address the new elements. The minimal AMT node is said to have a height of 0. Every node in an AMT has a height that indicates its distance from the leaf nodes. All leaf nodes have a height of 0. The height of the root node dictates the overall height of the entire AMT. In the case of the minimal AMT, this is 0. Elements are stored in a compacted form within nodes, they are "position-mapped" by a bitmap field that is stored with the node. The bitmap is a simple byte array, where each bit represents an element of the data that can be stored in the node. With a width of 8, the bitmap is a single byte and up to 8 elements can be stored in the node. The data array of a node _only stores elements that are present in that node_, so the array is commonly shorter than the maximum width. An empty AMT is a special-case where the single node can have zero elements, therefore a zero-length data array and a bitmap of `0x00`. In all other cases, the data array must have between 1 and width elements. Determining the position of an index within the data array requires counting the number of set bits within the bitmap up to the element we are concerned with. If the bitmap has bits 2, 4 and 6 set, we can see that only 3 of the bits are set so our data array should hold 3 elements. To address index 4, we know that the first element will be index 2 and therefore the second will hold index 4. This format allows us to store only the elements that are set in the node. Overflow beyond the single node AMT by adding an index beyond width-1 requires an increase in height in order to address all elements. If an element in the range of width to (width*2)-1 is added, a single additional height is required which will result in a new root node which is used to address two consecutive leaf nodes. Because we have an arity of up to width at any node, the addition of indexes in the range of 0 to (width^2)-1 will still require only the addition of a single additional height above the leaf nodes, i.e. height 1. From the width of an AMT we can derive the maximum range of indexes that can be contained by an AMT at any given `height` with the formula width^(height+1)-1. e.g. an AMT with a width of 8 and a height of 2 can address indexes 0 to 8^(2+1)-1=511. Incrementing the height doubles the range of indexes that can be contained within that structure. Nodes above height 0 (non-leaf nodes) do not contain terminal elements, but instead, their data array contains links to child nodes. The index compaction using the bitmap is the same as for leaf nodes, so each non-leaf node only stores as many links as it has child nodes. Because additional height is required to address larger indexes, even a single-element AMT will require more than one node where the index is greater than the width of the AMT. For a width of 8, indexes 8 to 63 require a height of 1, indexes 64 to 511 require a height of 2, indexes 512 to 4095 require a height of 3, etc. Retrieving elements from the AMT requires extracting only the portion of the requested index that is required at each height to determine the position in the data array to navigate into. When traversing through the tree, we only need to select from indexes 0 to width-1. To do this, we take log2(width) bits from the index to form a number that is between 0 and width-1. e.g. for a width of 8, we only need 3 bits to form a number between 0 and 7, so we only consume 3 bits per level of the AMT as we traverse. A simple method to calculate this at any height in the AMT (assuming bitWidth of 3, i.e. a width of 8) is: 1. Calculate the maximum number of nodes (not entries) that may be present in an sub-tree rooted at the current height. width^height provides this number. e.g. at height 0, only 1 node can be present, but at height 3, we may have a tree of up to 512 nodes (storing up to 8^(3+1)=4096 entries). 2. Divide the index by this number to find the index for this height. e.g. an index of 3 at height 0 will be 3/1=3, or an index of 20 at height 1 will be 20/8=2. 3. If we are at height 0, the element we want is at the data index, position-mapped via the bitmap. 4. If we are above height 0, we need to navigate to the child element at the index we calculated, position-mapped via the bitmap. When traversing to the child, we discard the upper portion of the index that we no longer need. This can be achieved by a mod operation against the number-of-nodes value. e.g. an index of 20 at height 1 requires navigation to the element at position 2, when moving to that element (which is height 0), we truncate the index with 20%8=4, at height 0 this index will be the index in our data array (position-mapped via the bitmap). In this way, each sub-tree root consumes a small slice, log2(width) bits long, of the original index. Adding new elements to an AMT may require up to 3 steps: 1. Increasing the height to accommodate a new index if the current height is not sufficient to address the new index. Increasing the height requires turning the current root node into an intermediate and adding a new root which links to the old (repeated until the required height is reached). 2. Adding any missing intermediate and leaf nodes that are required to address the new index. Depending on the density of existing indexes, this may require the addition of up to height-1 new nodes to connect the root to the required leaf. Sparse indexes will mean large gaps in the tree that will need filling to address new, equally sparse, indexes. 3. Setting the element at the leaf node in the appropriate position in the data array and setting the appropriate bit in the bitmap. Removing elements requires a reversal of this process. Any empty node (other than the case of a completely empty AMT) must be removed and its parent should have its child link removed. This removal may recurse up the tree to remove many unnecessary intermediate nodes. The root node may also be removed if the current height is no longer necessary to contain the range of indexes still in the AMT. This can be easily determined if _only_ the first bit of the root's bitmap is set, meaning only the left-most is present, which will become the new root node (repeated until the new root has more than the first bit set or height of 0, the single-node case). See https://github.com/ipld/specs/blob/master/data-structures/hashmap.md for a description of a HAMT algorithm. And https://github.com/ipld/specs/blob/master/data-structures/vector.md for a description of a similar algorithm to an AMT that doesn't support internal node compression and therefore doesn't support sparse arrays. Unlike a HAMT, the AMT algorithm doesn't benefit from randomness introduced by a hash algorithm. Therefore an AMT used in cases where user-input can influence indexes, larger-than-necessary tree structures may present risks as well as the challenge imposed by having a strict upper-limit on the indexes addressable by the AMT. A width of 8, using 64-bit integers for indexing, allows for a tree height of up to 64/log2(8)=21 (i.e. a width of 8 has a bitWidth of 3, dividing the 64 bits of the uint into 21 separate per-height indexes). Careful placement of indexes could create extremely sub-optimal forms with large heights connecting leaf nodes that are sparsely packed. The overhead of the large number of intermediate nodes required to connect leaf nodes in AMTs that contain high indexes can be abused to create perverse forms that contain large numbers of nodes to store a minimal number of elements. Minimal nodes will be created where indexes are all in the lower-range. The optimal case for an AMT is contiguous index values starting from zero. As larger indexes are introduced that span beyond the current maximum, more nodes are required to address the new nodes _and_ the existing lower index nodes. Consider a case where a width=8 AMT is only addressing indexes less than 8 and requiring a single height. The introduction of a single index within 8 of the maximum 64-bit unsigned integer range will require the new root to have a height of 21 and have enough connecting nodes between it and both the existing elements and the new upper index. This pattern of behavior may be acceptable if there is significant density of entries under a particular maximum index. There is a direct relationship between the sparseness of index values and the number of nodes required to address the entries. This should be the key consideration when determining whether an AMT is a suitable data-structure for a given application.

Package maglev implements maglev consistent hashing

Package blake2 provides a Go wrapper around an optimized, public domain implementation of BLAKE2. The cryptographic hash function BLAKE2 is an improved version of the SHA-3 finalist BLAKE. Like BLAKE or SHA-3, BLAKE2 offers the highest security, yet is fast as MD5 on 64-bit platforms and requires at least 33% less RAM than SHA-2 or SHA-3 on low-end systems.

Package muhash provides an implementation of a Multiplicative Hash, a cryptographic data structure that allows you to have a rolling hash function that you can add and remove elements from, without the need to re-serialize and re-hash the whole data set.

Amino is an encoding library that can handle interfaces (like protobuf "oneof") well. This is achieved by prefixing bytes before each "concrete type". A concrete type is some non-interface value (generally a struct) which implements the interface to be (de)serialized. Not all structures need to be registered as concrete types -- only when they will be stored in interface type fields (or interface type slices) do they need to be registered. All interfaces and the concrete types that implement them must be registered. Notice that an interface is represented by a nil pointer. Structures that must be deserialized as pointer values must be registered with a pointer value as well. It's OK to (de)serialize such structures in non-pointer (value) form, but when deserializing such structures into an interface field, they will always be deserialized as pointers. All registered concrete types are encoded with leading 4 bytes (called "prefix bytes"), even when it's not held in an interface field/element. In this way, Amino ensures that concrete types (almost) always have the same canonical representation. The first byte of the prefix bytes must not be a zero byte, so there are 2**(8*4)-2**(8*3) possible values. When there are 4096 types registered at once, the probability of there being a conflict is ~ 0.2%. See https://instacalc.com/51189 for estimation. This is assuming that all registered concrete types have unique natural names (e.g. prefixed by a unique entity name such as "com.tendermint/", and not "mined/grinded" to produce a particular sequence of "prefix bytes"). TODO Update instacalc.com link with 255/256 since 0x00 is an escape. Do not mine/grind to produce a particular sequence of prefix bytes, and avoid using dependencies that do so. Since 4 bytes are not sufficient to ensure no conflicts, sometimes it is necessary to prepend more than the 4 prefix bytes for disambiguation. Like the prefix bytes, the disambiguation bytes are also computed from the registered name of the concrete type. There are 3 disambiguation bytes, and in binary form they always precede the prefix bytes. The first byte of the disambiguation bytes must not be a zero byte, so there are 2**(8*3)-2**(8*2) possible values. The prefix bytes never start with a zero byte, so the disambiguation bytes are escaped with 0x00. Notice that the 4 prefix bytes always immediately precede the binary encoding of the concrete type. To compute the disambiguation bytes, we take `hash := sha256(concreteTypeName)`, and drop the leading 0x00 bytes. In the example above, hash has two leading 0x00 bytes, so we drop them. The first 3 bytes are called the "disambiguation bytes" (in angle brackets). The next 4 bytes are called the "prefix bytes" (in square brackets).

Package fastrand implements a cryptographically secure pseudorandom number generator. The generator is seeded using the system's default entropy source, and thereafter produces random values via repeated hashing. As a result, fastrand can generate randomness much faster than crypto/rand, and generation cannot fail beyond a potential panic at init. The method used in this package is similar to the Fortuna algorithm, which is used in used in FreeBSD for /dev/urandom. This package uses techniques that are known to be secure, however the exact implementation has not been heavily reviewed by cryptographers.

Murmur3 32bit hash function based on http://en.wikipedia.org/wiki/MurmurHash

Package ringpop is a library that maintains a consistent hash ring atop a gossip-based membership protocol. It can be used by applications to arbitrarily shard data in a scalable and fault-tolerant manner.

This is a exemplification on how to perform a P2WPKH transaction with Blinded Outputs using the PSET package with the assistance of vulpemventures/nigiri for funding the address, retrieving the UTXOs and broadcasting. You can run this example with this command. Check its behaviour on Nigiri's Esplora (http://localhost:5001/). First, we will need a Private Key and derive a Public key from it. We'll follow by generating a P2WPKH address. Secondly, we need to fund the address with some UTXOs we can use as inputs. This functions require Nigiri Chopsticks for the API calls. We need inputs and outputs in order to create a new PSET. The transaction will have 1 Input and 3 Outputs. The input we just funded from the faucet and three outputs. One for the ammount we want to send, one for the change and a last one for the fee. This is where the Creator Role takes part. We will create a new PSET with all the outputs that need to be blinded first. And then the Updater Role begins its part: We'll need to add the sighash type and witnessUtxo to the partial input. Next, we'll Blind the Outputs. This is where the Blinder Role takes part. This version of the blinder requires that all the private keys necessary to unblind all the confidential inputs used must be provided. We'll add the unblinded outputs now, that's only the fee output in this case. After we need a signature for the transaction. We'll get the double sha256 hash of the serialization of the transaction in order to then produce a witness signature for the given inIndex input and append the SigHash. Now we Update the PSET adding the input signature script and the pubkey. The Signer role handles this task as a function Sign of the *Updater type. The Finalizer role handles this part of the PSET. We'll combine every input's PartialSignature into the final input's SignatureScript. Now the partial transaction is complete, and it's ready to be extracted from the Pset wrapper. This is implented in the Extractor Role. Finally, our transaction is ready to be serialized and broadcasted to the network. The Broadcast function require Nigiri Chopsticks for the API call.

Package topk implements the Filtered Space-Saving TopK streaming algorithm The original Space-Saving algorithm: https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pdf The Filtered Space-Saving enhancement: http://www.l2f.inesc-id.pt/~fmmb/wiki/uploads/Work/misnis.ref0a.pdf This implementation follows the algorithm of the FSS paper, but not the suggested implementation. Specifically, we use a heap instead of a sorted list of monitored items, and since we are also using a map to provide O(1) access on update also don't need the c_i counters in the hash table. Licensed under the MIT license.

Package argon2 implements the key derivation function Argon2. Argon2 was selected as the winner of the Password Hashing Competition and can be used to derive cryptographic keys from passwords.

File Structures 2 This is a follow up to my crufty http://github.com/timtadh/file-structures work. That system has some endemic problems: 1. It uses the read/write interface to files. This means that it needs to do block management and cache management. In theory this can be very fast but it is also very challenging in Go. 2. Because it uses read/write it has to do buffer management. Largely, the system punts on this problem and allows go to handle the buffer management through the normal memory management system. This doesn't work especially well for the use case of file-structures. File Structures 2 is an experiment to bring Memory Mapped IO to the world of Go. The hypotheses are: 1. The operating system is good at page management generally. While, we know more about how to manage the structure of B+Trees, VarChar stores, and Linear Hash tables than the OS there is no indication that from Go you can acheive better performance. Therefore, I hypothesize that leaving it to the OS will lead to a smaller working set and a faster data structure in general. 2. You can make Memory Mapping performant in Go. There are many challenges here. The biggest of which is that there are no dynamically size array TYPES in go. The size of the array is part of the type, you have to use slices. This creates complications when hooking up structures which contain slices to mmap allocated blocks of memory. I hypothesize that this repository can acheive good (enough) performance here. The major components of this project: 1. fmap - a memory mapped file inteface. Part C part Go. Uses cgo. 2. bptree - a B+ Tree with duplicate key support (fixed size keys, variable length values) written on top of fmap. 3. slice - used by fmap and bptree to completely violate memory and type safety of Go. 4. errors - just a simple error package which maintains a stack trace with every error.

Package btcutil provides bitcoin-specific convenience functions and types. A Block defines a bitcoin block that provides easier and more efficient manipulation of raw wire protocol blocks. It also memoizes hashes for the block and its transactions on their first access so subsequent accesses don't have to repeat the relatively expensive hashing operations. A Tx defines a bitcoin transaction that provides more efficient manipulation of raw wire protocol transactions. It memoizes the hash for the transaction on its first access so subsequent accesses don't have to repeat the relatively expensive hashing operations. The Address interface provides an abstraction for a Bitcoin address. While the most common type is a pay-to-pubkey-hash, Bitcoin already supports others and may well support more in the future. This package currently provides implementations for the pay-to-pubkey, pay-to-pubkey-hash, and pay-to-script-hash address types. To decode/encode an address:

Package bloom implements Bloom Filter using double hashing

Package siphash implements the SipHash-64 and SipHash-128 pseudo-random-functions - with the recommended parameters: c = 2 and d = 4. SipHash computes a message authentication code (MAC) from a variable-length message and a 128 bit secret key. SipHash was designed to be efficient, even for short inputs, with performance comparable to non-cryptographic hash functions. SipHash cannot be used as a cryptographic hash function. Neither SipHash-64 nor SipHash-128 are strong collision resistant. SipHash was designed to defend hash flooding DoS attacks. SipHash-64 can be used as hashing scheme within hash maps or other key-value data structures. SipHash-128 can be used to compute a 128 bit authentication tag for messages.

Package merkletree implements a Merkle Tree capable of storing arbitrary content. A Merkle Tree is a hash tree that provides an efficient way to verify the contents of a set data are present and untampered with. At its core, a Merkle Tree is a list of items representing the data that should be verified. Each of these items is inserted into a leaf node and a tree of hashes is constructed bottom up using a hash of the nodes left and right children's hashes. This means that the root node will effictively be a hash of all other nodes (hashes) in the tree. This property allows the tree to be reproduced and thus verified by on the hash of the root node of the tree. The benefit of the tree structure is verifying any single content entry in the tree will require only nlog2(n) steps in the worst case. Creating a new merkletree requires that the type that the tree will be constructed from implements the Content interface. A slice of the Content items should be created and then passed to the NewTree method. t represents the Merkle Tree and can be verified and manipulated with the API methods described below.

Package cryptotools provides some abstract and easy-to-use interfaces to common cryptographic operations. It enables using one interface for a variety of underlying primitives, and without the hassle of setting them up. Available interfaces are: - HashToGroup: implementing hashing of arbitrary strings into prime-order groups, after hash-to-curve. - Hash: interface to hashing primitives and exposing common functions such as hashing, hmac, HKDF, and expand-only HKDF. - MHF: for memory hard function, a.k.a. password key derivation functions. - Encoding: for encoding and decoding to and from different formats.

Package sha3 implements the SHA-3 fixed-output-length hash functions and the SHAKE variable-output-length hash functions defined by FIPS-202. Both types of hash function use the "sponge" construction and the Keccak permutation. For a detailed specification see http://keccak.noekeon.org/ If you aren't sure what function you need, use SHAKE256 with at least 64 bytes of output. The SHAKE instances are faster than the SHA3 instances; the latter have to allocate memory to conform to the hash.Hash interface. If you need a secret-key MAC (message authentication code), prepend the secret key to the input, hash with SHAKE256 and read at least 32 bytes of output. The SHA3-x (x equals 224, 256, 384, or 512) functions have a security strength against preimage attacks of x bits. Since they only produce "x" bits of output, their collision-resistance is only "x/2" bits. The SHAKE-256 and -128 functions have a generic security strength of 256 and 128 bits against all attacks, provided that at least 2x bits of their output is used. Requesting more than 64 or 32 bytes of output, respectively, does not increase the collision-resistance of the SHAKE functions. A sponge builds a pseudo-random function from a public pseudo-random permutation, by applying the permutation to a state of "rate + capacity" bytes, but hiding "capacity" of the bytes. A sponge starts out with a zero state. To hash an input using a sponge, up to "rate" bytes of the input are XORed into the sponge's state. The sponge is then "full" and the permutation is applied to "empty" it. This process is repeated until all the input has been "absorbed". The input is then padded. The digest is "squeezed" from the sponge in the same way, except that output is copied out instead of input being XORed in. A sponge is parameterized by its generic security strength, which is equal to half its capacity; capacity + rate is equal to the permutation's width. Since the KeccakF-1600 permutation is 1600 bits (200 bytes) wide, this means that the security strength of a sponge instance is equal to (1600 - bitrate) / 2. The SHAKE functions are recommended for most new uses. They can produce output of arbitrary length. SHAKE256, with an output length of at least 64 bytes, provides 256-bit security against all attacks. The Keccak team recommends it for most applications upgrading from SHA2-512. (NIST chose a much stronger, but much slower, sponge instance for SHA3-512.) The SHA-3 functions are "drop-in" replacements for the SHA-2 functions. They produce output of the same length, with the same security strengths against all attacks. This means, in particular, that SHA3-256 only has 128-bit collision resistance, because its output length is 32 bytes.