getProofData method

Implementation

getProofData(List<int> knownLeavesIdxs) {
  final knownLeaves = knownLeavesIdxs.map((idx) => lookupEncoded[idx]).toList();

  final startingIdx = lookupEncoded.length - 1;
  final leafIdxs = knownLeavesIdxs.map((idx) => startingIdx + idx).toList();

  final proofIdxs = <int>[];
  if (leafIdxs.isNotEmpty) {
    final nLevels = getLevelFromIdx(leafIdxs.last);
    final splitPosition = pow(2, nLevels) - 1;
    final splitIdx = leafIdxs.indexWhere((x) => x >= splitPosition);

    if (splitIdx > 0) {
      final spliced = leafIdxs.sublist(splitIdx);
      leafIdxs.removeRange(splitIdx, leafIdxs.length);
      leafIdxs.insertAll(0, spliced);

      final splicedLeaves = knownLeaves.sublist(splitIdx);
      knownLeaves.removeRange(splitIdx, knownLeaves.length);
      knownLeaves.insertAll(0, splicedLeaves);
    }
  }

  var targetIdx = 0;
  void traverse(int nodeIdx) {
    if (targetIdx == leafIdxs.length) {
      proofIdxs.add(nodeIdx);
      return;
    }

    final target = leafIdxs[targetIdx];
    if (target == nodeIdx) {
      ++targetIdx;
      return;
    }

    final currentLevel = getLevelFromIdx(nodeIdx);
    final targetLevel = getLevelFromIdx(target);

    if (nodeIdx != getAncestorIdx(target, targetLevel - currentLevel)) {
      proofIdxs.add(nodeIdx);
      return;
    }

    final leftSon = 2 * nodeIdx + 1;
    traverse(leftSon);
    traverse(leftSon + 1);
  }

  traverse(0);

  return (
    leaves: knownLeaves,
    leafIndexes: leafIdxs,
    proofIndexes: proofIdxs,
  );
}