search

ricmoo / ethers-airdrop

A simple tool and library to deploy and manage a Merkle Air-Drop.
https://blog.ricmoo.com/merkle-air-drops-e6406945584d
93 stars 16 forks source link

Add Chunking Merkle Trees #2

Open ricmoo opened 6 years ago

ricmoo commented 6 years ago

This is a quick idea to break up the file, which will greatly increase the speed. At 1 million records it takes 20-30 minutes to completely collapse the merkle tree, necessary for both computing the merkle root and to compute any given single merkle proof; multiple merkle proofs could be solved at the same time, but the space requirements would be larger.

We can trivially break up a Merkle tree though; we will demonstrate with a smaller tree, with k = 16.


                                         P0
                    O0                                           O1
         N0                   N1                    N2                        N3
   M0         M1         M2         M3         M4          M5           M6           M7
L0    L1   L2    L3   L4    L5   L6    L7   L8    L9   L10    L11   L12    L13   L14    L15

Example 1: Chunk size C = 2 (8 chunk files, 1 root file)

Example 2: Chunk size C = 4 (4 chunks files, 1 root file)

For any given index, the file floor(index / C) and the root file are sufficient to reconstruct any merkle proof, the root is sufficient to compute the merkle root. C must be a power of 2.

For now we will support C = 1024, which in the case of 1 million records means each chunk is around 65kb and the root file is around 65kb, for a total of 1001 files.

NoahMarconi commented 6 years ago

Sounds great, I'm on it. I'll do a pull request once complete to let you review.

ricmoo commented 6 years ago

Cool. Could you maybe add a chunk command to the bin/ethers-airdrop.js as well, which will take in a normal airdrop-balances.json and spit out the chunked version? It's a lot easier to build a file similar to how the example does. I will provide some example files to play with. :)

NoahMarconi commented 6 years ago

For sure. Will include that in my update

NoahMarconi commented 6 years ago

Quick update so you know where everything is at. I've forked and added the basic additions here: https://github.com/NoahMarconi/ethers-airdrop

Going to work through some test cases and then add the command line chunk before I create a pull request.