elevenbuckets / elevenbuckets/OptractP2pCLI

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

Open
#17 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
JavaScript
Stars
0
Forks
1
PR merge metrics
No merged PRs in 30d

Description

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
1: /* anonymous */ [0x1b3eaa044da1] [events.js:~74] [pc=0x53c77374c56](this=0x092cc9a98ee1 )
2: Transform [0x26f0356abc79] [_stream_transform.js:~104] [pc=0x53c772fc3c1](this=0x092cc9a98ee1 ,options=0x3249176026f1 )
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`):

```javascript
'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);
```

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by running the attached test24proves.js with Node.js 10.15.3 and inspect makeMerkleTree(), comparing memory behavior near 2^20 and 2^21 leaves. Review merkleTreeValidator() and determine whether the issue should be resolved by supporting larger trees or by enforcing a one-million-transaction limit with validator rejection and block submission behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
javascript, node.js
Domain
backend, blockchain
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.