[WIP] 3072-bit MuHash based hash_serialized #10434

1. 
   sipa commented at 3:13 am on May 20, 2017: member

   This implements a 3072-bit MuHash discussed on https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html as a replacement for the hash_serialized field in gettxoutsetinfo.

   This is an order-independent hash, allowing it to be computed either by iterating over the UTXO set in non-sorted order. It also supports incremental addition and deletion of entries from the hash, allowing it to be updated on the fly for each block. Neither of these approaches is currently implemented.

2. in src/crypto/muhash.cpp:5 in e09131ecb6 outdated

   0@@ -0,0 +1,329 @@
   1+#include "muhash.h"
   

   ---

   ---

   

   paveljanik commented at 6:52 am on May 20, 2017:

   Copyright header missing

   ---

   

   sipa commented at 5:35 pm on May 21, 2017:

   Fixed.
3. in src/test/crypto_tests.cpp:521 in e09131ecb6 outdated

   518+    unsigned char out[384];
   519+
   520+    for (int i = 0; i < 10; ++i) {
   521+        unsigned char res[384];
   522+        int table[4];
   523+        for (int i = 0; i < 4; ++i) {
   

   ---

   ---

   

   paveljanik commented at 6:54 am on May 20, 2017:

   i shadowing.

   ---

   

   sipa commented at 5:36 pm on May 21, 2017:

   Fixed.
4. in src/test/crypto_tests.cpp:526 in e09131ecb6 outdated

   523+        for (int i = 0; i < 4; ++i) {
   524+            table[i] = insecure_rand_ctx.randbits(3);
   525+        }
   526+        for (int order = 0; order < 4; ++order) {
   527+            MuHash3072 acc;
   528+            for (int i = 0; i < 4; ++i) {
   

   ---

   ---

   

   paveljanik commented at 6:54 am on May 20, 2017:

   i shadowing
5. in src/test/crypto_tests.cpp:550 in e09131ecb6 outdated

   547+        z *= x; // x=X, y=Y, z=X
   548+        z /= y; // x=X, y=Y, z=X/Y
   549+        y /= x; // x=X, y=Y/X, z=X/Y
   550+        z *= y; // x=X, y=Y/X, z=1
   551+        z.Finalize(out);
   552+        for (int i = 0; i < 384; ++i) {
   

   ---

   ---

   

   paveljanik commented at 6:55 am on May 20, 2017:

   i shadowing

   ---

   

   sipa commented at 5:36 pm on May 21, 2017:

   Fixed.
6. 
   paveljanik commented at 6:56 am on May 20, 2017: contributor

   Release notes entry needed.
7. laanwj added the label RPC/REST/ZMQ on May 20, 2017
8. laanwj added the label UTXO Db and Indexes on May 20, 2017
9. sipa force-pushed on May 21, 2017
10. sipa force-pushed on May 21, 2017
11. sipa force-pushed on May 21, 2017
12. MuHash3072 implementation c11a333b43
13. muhash in gettxoutsetinfo c51afa3881
14. Simplification d24afe6b0c
15. Add x86_64 assembly optimization for MuHash 93f3680395
16. sipa force-pushed on Jun 30, 2017
17. 
    n1bor commented at 9:38 pm on January 1, 2018: none

    @sipa - did this POC of chainstate only sync: https://gist.github.com/n1bor/d5b0330a9addb0bf5e0f869518883522 https://botbot.me/freenode/bitcoin-core-dev/2016-10-24/?msg=75398575&page=3

    Worked well - syncs as fast at you can download chainstate db (30mins for 2.8gig chainstate). Network was the bottleneck. Should be able to rework to use MuHash easily - and rethink the snapshot interval/process. But if consensus is to NEVER commit chain-state to blockchain - then is all a little pointless. gmaxwell did suggest an expiring consensus rule so if want to change from MuHash would be easy - which would do.

    Or guess could compute hash by downloading every block! Then no security loss. But 150Gig download - so still 8hrs for 40Mbit connection. (think the hashing would take about 1 hour but in parallel with download).

18. 
    sipa commented at 7:13 pm on February 8, 2018: member

    Closing as stale.
19. sipa closed this on Feb 8, 2018

    ---

20. DrahtBot locked this on Sep 8, 2021

Contributors
sipa paveljanik n1bor

Labels
UTXO Db and Indexes RPC/REST/ZMQ