can only handle 1 million tx (~2^20) per block

[akaron]

In a "moderate-low" machine (my laptop: Intel core i5-8250U, bought in 2018, with 10GB+ ram available while testing, nodejs version 10.15.3), if there are more than 2 million (~2^21) transactions per block, then it's likely to see error messages as shown below. The test code is also attached in the end.

In theory, the data format can accept up to 2^24 transactions (see mfields, the max length of proves is 24), but the result here means in practice the limit is about one million (~2^20). If there are no obvious ways to optimize the code (especially the makeMerkleTree() part), then the maximum tx per block should be restricted to 1 million (no need to change existing code, just let validators reject tx and probably also submit block while there are already 1 million tx).

Here's the error message:

<--- Last few GCs --->

[3996:0x2ffb8c0]    77593 ms: Scavenge 1388.3 (1422.2) -> 1387.5 (1422.7) MB, 3.1 / 0.1 ms  (average mu = 0.167, current mu = 0.100) allocation failure
[3996:0x2ffb8c0]    77600 ms: Scavenge 1388.4 (1422.7) -> 1387.6 (1423.2) MB, 2.8 / 0.1 ms  (average mu = 0.167, current mu = 0.100) allocation failure
[3996:0x2ffb8c0]    77608 ms: Scavenge 1388.5 (1423.2) -> 1387.7 (1423.7) MB, 3.1 / 0.1 ms  (average mu = 0.167, current mu = 0.100) allocation failure

<--- JS stacktrace --->

==== JS stack trace =========================================

    0: ExitFrame [pc: 0x53c772dbe1d]
Security context: 0x1b3eaa01e6e9 <JSObject>
    1: /* anonymous */ [0x1b3eaa044da1] [events.js:~74] [pc=0x53c77374c56](this=0x092cc9a98ee1 <Keccak map = 0x2ea324731c9>)
    2: Transform [0x26f0356abc79] [_stream_transform.js:~104] [pc=0x53c772fc3c1](this=0x092cc9a98ee1 <Keccak map = 0x2ea324731c9>,options=0x3249176026f1 <undefined>)
    3: /* anonymous */ [0x32921267e4e1] [/home/kai/Work/project/Optrac...

FATAL ERROR: Ineffective mark-compacts near heap limit Allocation failed - JavaScript heap out of memory
 1: 0x8dc510 node::Abort() [node]
 2: 0x8dc55c  [node]
 3: 0xad9b5e v8::Utils::ReportOOMFailure(v8::internal::Isolate*, char const*, bool) [node]
 4: 0xad9d94 v8::internal::V8::FatalProcessOutOfMemory(v8::internal::Isolate*, char const*, bool) [node]
 5: 0xec7bf2  [node]
 6: 0xec7cf8 v8::internal::Heap::CheckIneffectiveMarkCompact(unsigned long, double) [node]
 7: 0xed3dd2 v8::internal::Heap::PerformGarbageCollection(v8::internal::GarbageCollector, v8::GCCallbackFlags) [node]
 8: 0xed4704 v8::internal::Heap::CollectGarbage(v8::internal::AllocationSpace, v8::internal::GarbageCollectionReason, v8::GCCallbackFlags) [node]
 9: 0xed7371 v8::internal::Heap::AllocateRawWithRetryOrFail(int, v8::internal::AllocationSpace, v8::internal::AllocationAlignment) [node]
10: 0xea07f4 v8::internal::Factory::NewFillerObject(int, bool, v8::internal::AllocationSpace) [node]
11: 0x114018e v8::internal::Runtime_AllocateInNewSpace(int, v8::internal::Object**, v8::internal::Isolate*) [node]
12: 0x53c772dbe1d
[2]    3996 abort (core dumped)  node test24proves.js

The test code here (the purpose of the code is to generate merkle tree with lots of leaves, in order to test whether merkleTreeValidator() in smart contract can handle long proves and sides):

'use strict';                                                                                                                             

const ethUtils = require('ethereumjs-utils');
const MerkleTree = require('merkle_tree');

const makeMerkleTree = (leaves) => {
    let merkleTree = new MerkleTree();
    merkleTree.addLeaves(leaves);
    merkleTree.makeTree();
    return merkleTree;
}

const getMerkleProof = (leaves, targetLeaf) => {
    let merkleTree = makeMerkleTree(leaves);

    let __leafBuffer = Buffer.from(targetLeaf.slice(2), 'hex');
    let txIdx = merkleTree.tree.leaves.findIndex( (x) => { return Buffer.compare(x, __leafBuffer) == 0 } );
    if (txIdx == -1) {
        console.log('Cannot find leave in tree!');
        return [];
    } else {
        console.log(`Found leave in tree! Index: ${txIdx}`);
    }

    let proofArr = merkleTree.getProof(txIdx, true);
    let proof = proofArr[1].map((x) => {return ethUtils.bufferToHex(x);});
    let isLeft = proofArr[0];

    let merkleRoot = ethUtils.bufferToHex(merkleTree.getMerkleRoot());
    return [proof, isLeft, merkleRoot];
}

let numLeaves = 2**21-1;  // error if use ~2^22 or more leaves
let leaves = Array.from({length: numLeaves}, (v, k) => ethUtils.bufferToHex(ethUtils.keccak256(k)));
let targetLeaf = leaves[100];
let proves; let sides; let merkleRoot;
[proves, sides, merkleRoot] = getMerkleProof(leaves, targetLeaf);

console.log(proves);
// console.log(sides);
let sideInt = sides.map((v, k)=>{return v===true ? 2**(sides.length-1-k) : 0}).reduce((_a, _b)=> _a+_b);
console.log(sideInt);
console.log(targetLeaf);
console.log(merkleRoot);

[akaron]

So, it's actually the limit of nodejs v8. By default, it is restricted to use only about 1.7GB of memory. Can change to a higher value by add an argument while run nodejs (see https://stackoverflow.com/questions/38558989/node-js-heap-out-of-memory ):

node --max-old-space-size=4096 yourFile.js

or set a environment variable (using bash as example):

export NODE_OPTIONS=--max_old_space_size=4096

But still, it took roughly half a minute if use 2^22 leaves (~4 million) to run the example script in previous comment (it basically generate merkle tree and then get the proof and side from the tree). It's still worth to optimize or at least restrict the amount of tx in a block.