An introduction to SIGMA the new ‘CPU friendly’ algorithm for Gulden

  1. Those whose eyes begin to roll back in their heads as they explain that any algorithm that can execute on a CPU can also have an ASIC constructed for it. That even if this were not the case ASIC resistance is undesirable because ASICs are the only true way to gain resistance to attack via botnet and so on…
  2. Those who swear that ASICs are the devil, that they lead to centralisation, push the common man out of crypto and should be fought at all costs. Quite often the people in the second group are oblivious too or choose to ignore the many failings or previous ‘ASIC resistant’ algorithms that have since had ASICs constructed for them.
  1. Having much more efficient ASICs renders a blockchain immune to botnets/government/well funded corporations; while a CPU only coin would be vulnerable to them.
  2. The up front costs of purchasing ASICs act as an additional deterrent to attackers.

Development of a new algorithm

In the search of a new algorithm I have read through numerous literature. I have read through the entire archives of the the PHC (Password Hashing Competition), I have read through forum/github/mailing lists of various other coins that have developed or are developing interesting new techniques and read the problems they have encountered, the pros/cons of their approaches and so forth.

SIGMA (Semi Iterated Global Memory Argon)

The high level functioning of SIGMA is as follows from a mining perspective:

  1. A miner assembles a valid block header.
  2. The full 32 bit nonce of the header is set to zero.
  3. Using repeated expensive hashing of the header, a large quantity of memory is filled up in smaller chunks based on the largest memory size we are willing to tolerate for an individual hash.
  4. The nonce is now treated as two separate halves that together total 32 bits, the ‘pre-nonce’ and the ’post-nonce’.
  5. The miner alters the pre-nonce, and performs an expensive hash on the modified header.
  6. The expensive hash from 5 is taken as the seed for a PRNG (Pseudo Random Number Generator) from which the miner sequentially generates 2^post-nonce-size sets of N random numbers. (65536 if post-nonce is 16 bits)
  7. As each set of N numbers is generated the miner sets the post-nonce to the current index and uses the set values as an index to a chunk of the global memory (which we treat as the same number of chunks as sets for this purpose).
  8. For each N in the set a chunk of global memory is hashed (along with the expensive hash and the modified header) using one of a selection of fast hash algorithms (also determined by the PRNG) and compared against the difficulty target.
  9. If a set of N values is found for which all the resulting fast hashes are lower than the difficulty target then a valid block has been found.
  10. The miner repeats 5–8 until a valid block is found
  11. If the miner exhausts the pre-nonce without success he updates the block data and starts again from step 1.
  1. The client receives a new header with nonce values already set.
  2. The client generates a single expensive hash for the header with pre-nonce.
  3. The client generates the PRNG set of N indices for the header with the post-nonce.
  4. The client performs another single expensive hash to generate the single required chunk of global memory.
  5. The client performs a single fast hash for the global chunk of memory.
  6. The client validates that the fast hash meets the difficulty target, if not the header can be discarded as invalid without any further work.
  7. Otherwise the client then re-uses the memory from (4) and performs another expensive hash and another fast hash to validate the second fast hash, and again checks it for validity.
  8. This continues for all N until the entire set is validated
  • The memory requirement of validation is constant, if the expensive hash is 16mb then validation can be done with roughly 16mb.
  • Validation is reasonably fast and allows to prevent DoS attacks, with invalid headers detectable with only 2 slow and 1 fast hashing operation.
  • Light clients on low power hardware can further reduce resource usage by opting to selectively/randomly validate only some of the hashes in the set and still be reasonably sure that they are not being sent down a path of false headers, effectively using less resources to validate than a malicious attacker would have to use to generate the string of false headers.
  • Initially we aim to require a 4gb global memory buffer — it is likely we will increase this to 8gb in the forseeable future.
  • For the expensive hashing we will use a modified Argon2d (argon2d_echo) with 16mb for the memory parameter; the reason for the deviation from plain argon is to prevent the re-use of any general purpose Argon ASICs that are manufactured.
  • The modification is that Echo is used in place of Blake for the initial and final phases in argon (Argon2 is designed to accommodate changes like this) while the bulk of the algorithm remains unchanged. The second change is to use it as a memory filler (to fill large amounts of memory) instead of only as a hash function (small memory output) — again this is completely within the design of Argon2 and not an invasive change.
    Echo is chosen for its heavy usage of AES (which most common CPUs have hardware acceleration for).
  • The PRNG is again AES based and designed to not allow for jumps. This is important to force post-nonce calculations to be (partially) sequential instead of paralleled complicating things for GPU implementations.
  • We have selected N=2 for now for the fast hashes; that is two fast hashes to be performed for every attempt. It is entirely possible that we will increase this in future.
  • We have also selected two fast hash algorithms, from which the random hash selection for the fast hashes can pick. Echo and Shavite both chosen for their similar performance and heavy usage of AES (which most common CPUs have hardware acceleration for).
    It is quite possible if not likely that we may add additional algorithms here in future.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store