[bisq-network/bisq] [WIP] Provide ASIC resistant PoW scheme for BSQ swaps (PR #5858)

[Steven Barclay]

<!-- 
- make yourself familiar with the CONTRIBUTING.md if you have not already (https://github.com/bisq-network/bisq/blob/master/CONTRIBUTING.md)
- make sure you follow our [coding style guidelines][https://github.com/bisq-network/style/issues)
- pick a descriptive title
- provide some meaningful PR description below
- create the PR
- in case you receive a "Change request" and/or a NACK, please react within 30 days. If not, we will close your PR and it can not be up for compensation.
- After addressing the change request, __please re-request a review!__ Otherwise we might miss your PR as we tend to only look at pull requests tagged with a "review required".
-->

This PR adds an implementation of the [Equihash](https://eprint.iacr.org/2015/946.pdf) memory-hard Proof of Work scheme for DoS/spam attack protection, to replace the present simple Hashcash scheme. It also adds a simple versioning system to make it easier to migrate from one algorithm to another in case of failure to provide adequate DoS attach protection, that is, if an attacker spamming the BSQ swap offer book has too much of a speed/efficiency advantage over an honest user, e.g. due to use of FPGAs, GPUs, etc.

The Equihash scheme is _asymmetric_, meaning that producing a PoW by solving a hashing puzzle is slow and consumes up to MBs of memory, but verification is instant. The puzzle solutions are larger than that of the present Hashcash scheme (where it is just a 64-bit counter/nonce) but still fairly small - 10's of bytes to a few kB in size, depending on the puzzle parameters. So they shouldn't bloat the BSQ swap offer payloads significantly.

You can view, comment on, or merge this pull request online at:

  https://github.com/bisq-network/bisq/pull/5858

-- Commit Summary --

  * Code cleanup: remove unused PoW class & test
  * Code cleanup: replace (Bi)Function<..,Boolean> with (Bi)Predicate<..>
  * Add Equihash implementation for use in ASIC-resistant PoW
  * Add Equihash.IntListMultimap (private) class for speedup
  * Further Equihash optimisation: avoid lambda+stream in tight loop
  * Further Equihash optimisation: partial parallelisation

-- File Changes --

    A common/src/main/java/bisq/common/crypto/Equihash.java (397)
    M common/src/main/java/bisq/common/crypto/HashCashService.java (30)
    D common/src/main/java/bisq/common/crypto/ProofOfWorkService.java (156)
    M common/src/main/java/bisq/common/util/PermutationUtil.java (12)
    M common/src/main/java/bisq/common/util/Utilities.java (29)
    A common/src/test/java/bisq/common/crypto/EquihashTest.java (71)
    D common/src/test/java/bisq/common/crypto/ProofOfWorkServiceTest.java (81)
    M common/src/test/java/bisq/common/util/PermutationTest.java (9)
    M core/src/main/java/bisq/core/dao/governance/voteresult/VoteResultService.java (4)
    M core/src/main/java/bisq/core/filter/FilterManager.java (8)
    M core/src/main/java/bisq/core/network/CoreNetworkFilter.java (10)
    M core/src/main/java/bisq/core/payment/PaymentAccounts.java (8)
    M core/src/main/java/bisq/core/trade/bisq_v1/FailedTradesManager.java (6)
    M p2p/src/main/java/bisq/network/p2p/network/NetworkFilter.java (4)

-- Patch Links --

https://github.com/bisq-network/bisq/pull/5858.patch
https://github.com/bisq-network/bisq/pull/5858.diff

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/bisq-network/bisq/pull/5858
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.bisq.network/pipermail/bisq-github/attachments/20211123/ece43d2c/attachment.htm>