Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Use a unique PoW algorithm #506

Open
PlasmaPower opened this issue Jan 18, 2018 · 33 comments

Comments

Projects
None yet
@PlasmaPower
Copy link
Contributor

commented Jan 18, 2018

There are blake2b ASICs coming out with very high hash rates. These are being developed to mine coins such as siacoin. In order to avoid these being used to spam the RaiBlocks network, we should use a unique PoW algorithm. With a unique PoW algorithm, there would be much less of an incentive to develop ASICs for this unique algorithm, as you cannot make money by consistently spamming RaiBlocks.

I propose (pseudocode): blake2b(blake2b(input) ^ b"RaiBlocks"). As this is approximately twice as difficult to compute (compared to just blake2b, the current algorithm), I'd recommend also halving the difficulty.

@george-viaud

This comment has been minimized.

Copy link

commented Jan 18, 2018

How do you check PoW for this (What is the inverse operation or check operation?) Likely a very obvious answer - I'm just curious

@bradennapier

This comment has been minimized.

Copy link
Contributor

commented Jan 18, 2018

I was lucky enough to score a A3 when it first became available (sold out in 15 minutes). I should have mine within about 9 days in California - but those in China likely already have them. To provide a link to the product page:

https://shop.bitmain.com/productDetail.htm?pid=00020180116164357365a2ljX8gx06D3

Sia is rumored to be releasing one that will be far more powerful but very specific to SiaCoin (16nm) with 7nm ASICs on the way this year, we definitely want to make sure we are covered. Even if the A3 couldn't be purposed for an attack, it will still be a concern that is raised often when people see Blake2b.

Would be nice to change the algo regardless so it isn't an issue.

@PlasmaPower posted a calculation of the A3 as:

my calculations: (2^64 - 0xffffffc000000000)/(2^64) * 815e9
which turns out to be 12k tx/s

for a single A3 unit.

@PlasmaPower

This comment has been minimized.

Copy link
Contributor Author

commented Jan 18, 2018

@george-viaud What I posted there is the algorithm for checking PoW. Calculating PoW is just trying a bunch of different possible work values, until you find one that works.

@george-viaud

This comment has been minimized.

Copy link

commented Jan 18, 2018

Ahh that's how it works. Interesting. Thanks!

@Nevsor

This comment has been minimized.

Copy link

commented Jan 18, 2018

I do not know much about ASIC development, but how expensive would it be to tweak the design for a regular blake2b ASIC to compute blake2b(blake2b(input) ^ b"RaiBlocks")? Shouldn't the changes needed be relatively small, because most of the circuitry remains the same (the blake2b function) and the changes are rather trivial (xor with a constant and two evaluations of the blake2b instead of one)? Why not use a memory-hard hash function like scrypt (scrypt(scrypt(input) ^ b"RaiBlocks"))? This should make the use of specialised hardware to spam the network even harder.

@PlasmaPower

This comment has been minimized.

Copy link
Contributor Author

commented Jan 18, 2018

You make a good point about modifying blake2b ASICs. There are scrypt ASICs though. Perhaps we should use a multi-algo function, not because it's inherently ASIC resistant, but because it could be very unique.

@PlasmaPower

This comment has been minimized.

Copy link
Contributor Author

commented Jan 18, 2018

Looking at the pseudocode for blake2b on Wikipedia, I believe we could modify the Mix function by swapping the arguments x and y (as named in Wikipedia's pseudocode). Alternatively, we could modify one of the rotate amounts in that function.

I'm no expert here, but I believe these changes would significantly alter the function, while still preserving its cryptographic properties.

@Nevsor

This comment has been minimized.

Copy link

commented Jan 18, 2018

I do not like the idea of reimplementing existing and tested cryptographic functions for the sake of being unique. Regarding your specific change suggestion: I do not think that changing x and y will have an significant effect on the cost to spam the network. It will only result in swapping every other byte of the plaintext message with it successor. Therefore an attacker could just do this swap in the block bytes he wants to send, give the resulting message to an usual blake2b ASIC and reverse the swap (including the nonce found by the ASIC) and he will get a valid proof of work for the altered blake2b function. This only requires very small changes to the spamming software and none to the ASIC!

@ragardner

This comment has been minimized.

Copy link
Contributor

commented Jan 18, 2018

I'm not an expert on cryptography but it seems to me the logical long term solution would be to use a combination of two very different algorithms for PoW to mitigate the use of a single machine designed for one algorithm

If this is even possible...

@osaund

This comment has been minimized.

Copy link

commented Jan 18, 2018

I agree with @Nevsor, re-implementing an existing crypto algorithm seems risky.

If you used a multi algo, would it be performed in parallel (multiple results) or serial? And in either case why couldn't an attacker use multiple ASICs?

@FSMaxB

This comment has been minimized.

Copy link

commented Jan 18, 2018

If anything, a memory hard algorithm like Argon2i should be used. This would eliminate most of the concerns that ASICS could be used to spam the network.

@PlasmaPower

This comment has been minimized.

Copy link
Contributor Author

commented Jan 18, 2018

Memory hard algorithms are a step in the right direction, but are not a perfect solution.

@FSMaxB

This comment has been minimized.

Copy link

commented Jan 18, 2018

I just found out that @Nevsor has written exactly the same.

@Nevsor

This comment has been minimized.

Copy link

commented Jan 18, 2018

I think Argon2d might be a good choice as a PoW algorithm. @FSMaxB Argon2i is optimized to be resistant to side-channel attacks, while Argon2d is resistant to cracking with specialized hardware. Proof of Work needs the later, while the former is quite irrelevant. Argon2 would also give us the opportunity to adjust the memory requirements for computing the PoW in addition to the time requirement (difficulty) to keep up with hardware improvements.

Simply changing Blake2b for Argon2d should make the network much more spam resistant. Who decides whether this gets implemented?

The change to a "unique" combination of algorithms like @PlasmaPower proposed could still be implemented if it is found worthwhile.

@PlasmaPower

This comment has been minimized.

Copy link
Contributor Author

commented Jan 18, 2018

@Nevsor I modified blake2b with my suggestion of changing the order of x and y in the mix function, and as I thought, it significantly changed the result. Changing the byte order did not affect it. However, I do think that changing the rotation amounts would be a better change.

Here are the results of swapping x and y in the mix function, using an 8 byte output as the PoW calculations do.

Blake2b hash of an empty string: E4A6A0577479B2B4
Blake2b hash of ab in ASCII: 0E52B5F187DE1088
Blake2b hash of ba in ASCII: EE3F6B40991A6C7A

Next I tested it with the modified mix function.

Mix modified blake2b hash of an empty string: E17D1F1ECEDE1923
Mix modified blake2b hash of ab in ASCII: FAFD51206B6688D0
Mix modified blake2b hash of ba in ASCII: 5ADE3D6D0ED11A47

After that I reverted the mix changes and changed the rotation amounts from 32, 24, 16, 63 to the rotation amounts used in the original Blake: 32, 25, 16, 11. As specified in the Blake2 paper section 2.2 "Rotations optimized for speed", the rotation amounts were only changed in Blake2 for speed.

Rotation modified blake2b hash of an empty string: 291CD5FF2FADEB27
Rotation modified blake2b hash of ab in ASCII: 18E7542989D2E725
Rotation modified blake2b hash of ba in ASCII: 86E2200F4CAE66FE

Note: this section has been edited. Previously I just changed one rotation.

I prefer the change of the rotation amounts, since the Blake2 paper indicates that it preserves security.

@develerltd

This comment has been minimized.

Copy link

commented Jan 20, 2018

Personally I'd choose either something like what monero uses, or the algo that vertcoin uses. Both have been proven cryptographically secure. The later lyra2 contains a lot of parameters that can be adjusted.

@FSMaxB

This comment has been minimized.

Copy link

commented Jan 20, 2018

@develerltd Argon2 was the winner of the password hashing contest, so it has undergone quite some scrutiny by cryptographers.

Note though that no practical cryptographical algorithm can be proven secure. (one time pads are proven secure for example, but they are not practical).

@develerltd

This comment has been minimized.

Copy link

commented Jan 20, 2018

@bradennapier

This comment has been minimized.

Copy link
Contributor

commented Jan 20, 2018

Wait where did we end up with cuckoo? Seems like a really great option and from my discussion with Colin he is also a fan. May be interesting to look at some combination using Cuckoo in the mix. Would surely be unique, no?

@pocesar

This comment has been minimized.

Copy link

commented Jan 20, 2018

having multiple algorithms doesn't actually stop ASICs from being made. see X10 and X11 ASICs. even if you mix 2-3 "unique" algos in a chain, it's just a matter of time for somebody to come with an ASIC for it.
the algo(s) can't rely on being only computationally expensive, argon2 does it all, because it has diminishing returns https://password-hashing.net/argon2-specs.pdf
so my vote would be on argon2 as well

@george-viaud

This comment has been minimized.

Copy link

commented Jan 22, 2018

What if transactions (at least below a particular threshold) required some sort of collateral that would be automatically released / returned to the sending account under conditions of non-quorum after a period of time after being first seen? The idea to increase risk for bad actors, especially in the event of double-spend attempts (forcing quorum) w/ small transactions (or even large?) Obviously not a fully-formed idea - just thought it may have some value with further thought.

@icarusglider

This comment has been minimized.

Copy link
Contributor

commented Jan 22, 2018

The application of hashes and nonces in the Sia algorithm is sufficiently different than how ours is used to be completely incompatible. ASICs are "Application Specific", which means they are optimized as much as possible for that algorithm such that minimal data is passed to the chip to be processed. Thus, using the chips as generic blake2b hashing machines would be inefficient and tax the data bus to each chip.

Rather, the design would have been optimized on FPGA to take the minimal input data and do as much of the algorithm as quickly as possible, either returning nothing or a solution. Thus the data to start with would be sent out to every ASIC chip (many on the board in parallel) and all work on the solution at the same time.

While we use the same hashing algorithm the pow algorithm is vastly different.

@clemahieu

This comment has been minimized.

Copy link
Collaborator

commented Feb 1, 2018

To bring up cuckoo cycle throttling, has anyone investigated this or know of any obvious issues? From the description it seems to resist ASICs. https://github.com/tromp/cuckoo

Two concerns I'd like to look at:

  1. Is the proof size variable length?
  2. Is the proof size large?

This was referenced Aug 23, 2018

@rkeene rkeene self-assigned this Aug 25, 2018

@rkeene rkeene added this to the V17.0 milestone Aug 25, 2018

@rkeene

This comment has been minimized.

Copy link
Contributor

commented Aug 31, 2018

See also issue #1064

@rkeene

This comment has been minimized.

Copy link
Contributor

commented Oct 12, 2018

We are going to be pushing moving to a different work calculation mechanism down the road. For now we will prioritize blocks to vote on based on their work (#1298), use a dynamic floor (#196), and in the future come up with a different work mechanism (this issue).

@rkeene rkeene modified the milestones: V17.0, V20.0 Oct 12, 2018

@funkspock

This comment has been minimized.

Copy link

commented Dec 25, 2018

@clemahieu Cuckoo Cycle is no longer considered ASIC resistant (article by the author: John Tromp)
"I now claim Cuckoo Cycle to be ASIC friendly. Its main quality is that it is the simplest possible PoW, and that it functions as a proof of SRAM."
https://forum.aeternity.com/t/cuckoo-cycle-no-longer-considered-asic-resistant/814

Grin initially opted to use the new Cuckoo Cycle PoW algorithm, also purported to be ASIC resistant due to being memory latency bound. This means that the algorithm is bound by memory bandwidth rather than raw processor speed with the hope that it will make mining possible on commodity hardware. In August 2018 the Grin team made an announcement that they have become aware that it was likely that an ASIC would be available for the Cuckoo cycle algorithm at launch of their mainnet. While they acknowledge that ASIC mining is inevitable they are concerned that the current ASIC market is very centralized (i.e. Bitmain).
https://forum.hypernum.com/threads/grin-vs-beam-a-comparison.208/

Initially, Grin intended to use 2 PoW algorithms (which sounds like a novel approach): Each block mined with the primary Proof-of-Work tends to increase the secondary scaling factor, meaning that every time a “primary” block is found it gets easier and easier to mine with the secondary proof-of-work algorithm. In contrast, when a “secondary” block is found the secondary scaling factor tend to reduce. Which means that it gets harder to mine with the secondary PoW (since you need a higher solution difficulty to reach to the target difficulty) and easier to mine with the primary proof-of-work.
https://blog.blockcypher.com/an-introduction-to-grin-proof-of-work-103aaa9f66ce

My vote, same as @Nevsor and @FSMaxB would goto Argon2d which is specifically designed for cryptocurrencies.
https://github.com/P-H-C/phc-winner-argon2/blob/master/argon2-specs.pdf

@clemahieu

This comment has been minimized.

Copy link
Collaborator

commented Dec 26, 2018

I considered argon early on but the issue I ran in to was the verification wasn’t trivial. It took the same large amount of memory to verify as it does to generate a single round. We use argon2 for the key derivation function which benefits from this slow verification. Has argon added a fast verification node?

@funkspock

This comment has been minimized.

Copy link

commented Dec 26, 2018

@clemahieu Fast hash verification aka The Merkle-tree-based PoW based on Argon2 (called MTP) has recently been implemented by Zcoin.

The MTP-Argon2 requires 2 GB of RAM to make a proof, and can be initialized and start producing proofs in less than 1 second – performance hardly beaten by competitors like Equihash for the same amount of RAM.

Development of MTP originally began in 2017. After researchers had found issues in the original paper, Zcoin launched several bounties to address both issues at the theoretical level as well as in the implementation. The original researchers successively addressed the first version’s issues including further enhancements with their revised paper partially funded by Zcoin and published in January 2018. Zcoin released the first public version of MTP on their testnet in May. Since then it has been tested and refined and went on their mainnet on 10 Dec. 2018.

Link below contains links to the revised academic paper and their bounty program results
https://zcoin.io/mtp-zcoins-new-proof-of-work-algorithm

Link to source code
https://github.com/zcoinofficial/zcoin/tree/master/src/crypto/MerkleTreeProof

@clemahieu

This comment has been minimized.

Copy link
Collaborator

commented Dec 29, 2018

After briefly reading over the paper this seems to address the issues I had with using the argon2 kdf for PoW generation.

I'm going to do another pass on the paper and some of the source code in the next few days. Do they have an implementation outside the zcoin repository? It looks like their repository is covered under a general MIT license though it'd be nice if they had plans to separate it out.

@funkspock

This comment has been minimized.

Copy link

commented Dec 30, 2018

@clemahieu I wasnt able to find any other implementation, the researchers seem to have collaborated with zcoin for their revised paper. Maybe there are opportunities to build further on what zcoin has coded or do a collaboration so that synergies in terms of sharing experiences can be exchanged? (depending on code quality and zcoin's willingness to collaborate), on the other hand maybe its better to code a new clean implementation and perhaps collaborate with the researchers.

@clemahieu

This comment has been minimized.

Copy link
Collaborator

commented Feb 18, 2019

The proofs look rather large:

    uint8_t hashRootMTP[16]; // 16 is 128 bit of blake2b
    uint64_t nBlockMTP[mtp::MTP_L*2][128]; // 128 is ARGON2_QWORDS_IN_BLOCK
    std::deque<std::vector<uint8_t>> nProofMTP[mtp::MTP_L*3];
    constexpr int8_t MTP_L = 64;
@nano-ark

This comment has been minimized.

Copy link

commented Mar 8, 2019

chanced upon Itsuku which claims to have 1/16th the proof size. couldn't find any implementation except for this python library though

@funkspock

This comment has been minimized.

Copy link

commented Mar 8, 2019

@nano-ark "Although the benchmarks of Itsuku are not available, we could
guesstimate that the 32-fold increase in the number of memory accesses would result in 10-15x decrease in performance. Therefore, to fit in 1 second Itsuku would have to be run with 100-200 MiB at most."
(section 4.6, page 9 https://arxiv.org/pdf/1606.03588.pdf)
MTP authors actually refer to Itsuku in their paper (hinting that it does not align with the memory-hard function concept), Proof sizes are indeed smaller: MTP-Argon2 186 KiB vs Itsuku 11 KiB

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.