@web3-storage/data-segment - npm Package Compare versions

Comparing version 2.0.0 to 2.1.0

dist/src/aggregate.d.ts

@@ -59,3 +59,3 @@ export const MAX_CAPACITY: bigint;
      */
-    estimate({ root, size }: API.PieceInfo): API.Result<{
+    estimate({ link, size }: API.PieceInfo): API.Result<{
         parts: [API.MerkleTreeNodeSource];
@@ -72,3 +72,3 @@ offset: API.uint64;
      * @param {number} source.limit
-     * @param {API.MerkleTree} source.tree
+     * @param {API.AggregateTree} source.tree
      */
@@ -80,5 +80,5 @@ constructor({ tree, parts, limit, size, offset }: {
         limit: number;
-        tree: API.MerkleTree;
+        tree: API.AggregateTree;
     });
-    tree: API.MerkleTree<number | bigint>;
+    tree: API.AggregateTree<bigint>;
     parts: API.MerkleTreeNodeSource[];
@@ -88,2 +88,3 @@ limit: number;
     offset: bigint;
+    link: API.PieceLink;
     /**
@@ -93,10 +94,13 @@ * Size of the index in bytes.
     get indexSize(): number;
-    link(): API.PieceLink;
+    /**
+     * Height of the perfect binary merkle tree corresponding to this aggregate.
+     */
+    get height(): number;
     toJSON(): {
         link: {
-            '/': import("multiformats").ToString<import("multiformats").Link<API.MerkleTreeNode, 61697, 4114, import("multiformats").Version>, string>;
+            '/': API.ToString<import("multiformats").Link<API.MerkleTreeNode, 61697, 4114, import("multiformats").Version>, string>;
         };
-        size: number;
+        height: number;
     };
 }
 //# sourceMappingURL=aggregate.d.ts.map

dist/src/aggregate/tree.d.ts

 /**
- * We allow up to 2 ** 60 leafs in the tree, with is greater than then
- * Number.MAX_SAFE_INTEGER ((2 ** 53) - 1) which is why we need to use
- * uint64s.
+ * We limit tree height to 60, since we have a perfect binary merkle tree this
+ * will fit up to 2 ** 60 of leafs nodes.
  */
-export const MAX_LOG2_LEAFS: 60;
-export function create(log2Leafs: number): API.AggregateTree;
+export const MAX_HEIGHT: 60;
+export function create(height: number): API.AggregateTree;
 export function batchSet(tree: API.MerkleTreeBuilder, values: API.MerkleTreeNodeSource[]): void;
 export function clear(tree: AggregateTree): void;
-export function idxFor(maxLevel: number, level: number, index: API.uint64): API.uint64;
+export function idxFor(height: number, level: number, index: API.uint64): API.uint64;
 export type Model = {
-    log2Leafs: number;
+    height: number;
     data: SparseArray<API.MerkleTreeNode>;
 };
 import * as API from '../api.js';
-declare class AggregateTree {
+/**
+ * @implements {API.AggregateTree}
+ */
+declare class AggregateTree implements API.AggregateTree {
     /**
+     * @param {number} height
+     * @param {SparseArray<API.MerkleTreeNode>} data
+     */
+    constructor(height: number, data?: SparseArray<API.MerkleTreeNode>);
+    /**
      * The sparse array contains the data of the tree. Levels of the tree are
      * counted from the leaf layer (layer 0).
-     * Where the leaf layer lands depends on the `log2Leafs` value.
-     * The root node of a the tree is stored at position [1].
      *
-     * @param {number} log2Leafs
-     * @param {SparseArray<API.MerkleTreeNode>} data
+     * Where the leaf layer lands depends on the `height` of the tree.
      */
-    constructor(log2Leafs: number, data?: SparseArray<API.MerkleTreeNode>);
-    log2Leafs: number;
     data: SparseArray<API.MerkleTreeNode>;
-    get maxLevel(): number;
+    height: number;
     get leafCount(): bigint;
-    get depth(): number;
     get root(): API.MerkleTreeNode;
@@ -58,13 +59,14 @@ /**
  * @template T
+ * @implements {API.SparseArray<T>}
  */
-declare class SparseArray<T> {
+declare class SparseArray<T> implements API.SparseArray<T> {
     /**
-     * @param {Map<API.uint64, T[]>} subs
+     * @param {Map<API.uint64, T[]>} shards
      */
-    constructor(subs?: Map<API.uint64, T[]>);
+    constructor(shards?: Map<API.uint64, T[]>);
     /**
      * @private
      */
-    private subs;
-    clear(): void;
+    private shards;
+    clear(): this;
     /**
@@ -79,3 +81,3 @@ * @param {API.uint64} index
      */
-    set(index: API.uint64, value: T): void;
+    set(index: API.uint64, value: T): this;
     /**
@@ -82,0 +84,0 @@ * @param {API.uint64} start

dist/src/api.d.ts

@@ -1,2 +0,3 @@
-import type { Link } from 'multiformats/link';
+import type { Link, ToString } from 'multiformats/link';
+export { ToString };
 /**
@@ -49,7 +50,2 @@ * Implementers of the `Read` interface are called "readers". Readers
 }
-export interface AggregateState {
-    capacity: number;
-    offset: number;
-    parts: MerkleTreeNodeSource[];
-}
 export interface Vector<T> extends Iterable<T> {
@@ -77,6 +73,2 @@ append(value: T): Vector<T>;
     /**
-     * The Depth of the tree. A single-node tree has depth of 1
-     */
-    depth: number;
-    /**
      * Amount of leafs in this Merkle tree.
@@ -86,2 +78,6 @@ */
     /**
+     * Height of the tree.
+     */
+    height: number;
+    /**
      * Root node of this Merkle tree.
@@ -108,4 +104,4 @@ */
 }
-export interface AggregateTree extends MerkleTree<uint64>, MerkleTreeBuilder<uint64> {
-    collectProof(level: number, index: uint64): ProofData;
+export interface AggregateTree<I extends uint64 | number = uint64> extends MerkleTree<I>, MerkleTreeBuilder<I> {
+    collectProof(level: number, index: I): ProofData;
 }
@@ -117,3 +113,3 @@ export interface PieceInfo {
      */
-    root: MerkleTreeNode;
+    link: PieceLink;
     /**
@@ -124,22 +120,32 @@ * Size is the number of padded bytes that is contained in this piece.
 }
-export interface Piece extends PieceInfo {
-    link(): PieceLink;
-    toJSON(): {
-        link: {
-            '/': string;
-        };
-        size: number;
-    };
+export interface PieceInfoView extends PieceInfo {
+    /**
+     * Height of the perfect binary merkle tree representing
+     * this piece.
+     */
+    height: number;
 }
-export interface ContentPiece extends Piece {
+/**
+ * Represents a piece tree and underlying merkle tree.
+ */
+export interface Piece extends PieceInfoView {
+    tree: PieceTree;
+    /**
+     * Size of the payload from which this piece was derived.
+     */
     contentSize: number;
+    /**
+     * Size after 0 padding to next power of 2.
+     */
     paddedSize: number;
-    toJSON(): {
-        link: {
-            '/': string;
-        };
-        contentSize: number;
-        paddedSize: number;
-        size: number;
+    /**
+     * Returns a JSON representation of this piece.
+     */
+    toJSON(): PieceJSON;
+}
+export interface PieceJSON {
+    link: {
+        '/': string;
     };
+    height: number;
 }
@@ -229,4 +235,20 @@ export type PieceLink = Link<MerkleTreeNode, 0xf101, 0x1012>;
      */
-    leafs: number;
+    height: number;
 }
+export interface AggregateTreeData {
+    /**
+     * Height of the (perfect binary) tree.
+     */
+    height: number;
+    /**
+     * Sparse array that contains tree nodes. Levels
+     * of the tree are counted from the leaf layer (0).
+     */
+    data: SparseArray<MerkleTreeNode>;
+}
+export interface SparseArray<T> {
+    clear(): this;
+    at(index: uint64): T | undefined;
+    set(index: uint64, value: T): this;
+}
 export interface ProofData {
@@ -323,3 +345,2 @@ path: MerkleTreeNode[];
 }[keyof U];
-export {};
 //# sourceMappingURL=api.d.ts.map

dist/src/piece.d.ts

@@ -10,16 +10,16 @@ /**
 /**
- * MaxLayers is the current maximum height of the rust-fil-proofs proving tree.
+ * Current maximum piece size is limited by the maximum number of leaves in the
+ * tree, which is limited by max size of the JS array, which is 128GiB.
  */
-export const MAX_LAYERS: 31;
-/**
- * Current maximum size of the rust-fil-proofs proving tree.
- */
 export const MAX_PIECE_SIZE: number;
 /**
- * MaxPiecePayload is the maximum amount of data that one can compute commP for.
- * Constrained by the value of {@link MAX_LAYERS}.
+ * The maximum amount of data that one can compute for the piece.
  */
-export const MAX_PIECE_PAYLOAD: number;
+export const MAX_PAYLOAD_SIZE: number;
+export function toJSON(piece: API.PieceInfo): API.PieceJSON;
+export function fromJSON({ link, height }: API.PieceJSON): API.PieceInfoView;
+export function toString(piece: API.PieceInfo): API.ToString<API.PieceJSON>;
+export function fromString(source: API.ToString<API.PieceJSON> | string): API.PieceInfoView;
 export function createLink(root: API.MerkleTreeNode): API.PieceLink;
-export function build(source: Uint8Array): API.ContentPiece;
+export function build(source: Uint8Array): API.Piece;
 import * as Tree from './piece/tree.js';
@@ -29,3 +29,39 @@ import * as UnpaddedSize from './piece/unpadded-size.js';
 import * as API from './api.js';
+/**
+ * @param {API.PieceInfo} piece
+ */
+declare class PieceInfo {
+    /**
+     * @param {object} data
+     * @param {API.PieceLink} data.link
+     * @param {number} data.height
+     */
+    constructor({ link, height }: {
+        link: API.PieceLink;
+        height: number;
+    });
+    link: API.PieceLink;
+    height: number;
+    get size(): bigint;
+    toJSON(): API.PieceJSON;
+    toString(): API.ToString<API.PieceJSON>;
+}
+/**
+ * @implements {API.Piece}
+ */
+declare class Piece extends PieceInfo implements API.Piece {
+    /**
+     * @param {object} data
+     * @param {number} data.contentSize
+     * @param {API.PieceTree} data.tree
+     */
+    constructor({ contentSize, tree }: {
+        contentSize: number;
+        tree: API.PieceTree;
+    });
+    contentSize: number;
+    tree: API.PieceTree;
+    get paddedSize(): number;
+}
 export { Tree, UnpaddedSize, PaddedSize };
 //# sourceMappingURL=piece.d.ts.map

dist/src/piece/padded-size.d.ts

 export function from(size: number | API.uint64): API.PaddedPieceSize;
 export function validate(size: API.uint64): API.Result<API.PaddedPieceSize, RangeError>;
 export function toUnpaddedSize(size: API.PaddedPieceSize): API.UnpaddedPieceSize;
+export function toHeight(size: API.PaddedPieceSize): number;
 import * as API from '../api.js';
 //# sourceMappingURL=padded-size.d.ts.map

dist/src/piece/tree.d.ts

 /**
- * `newBareTree` allocates that memory needed to construct a tree with a
- * specific amount of leafs.
+ * Allocates a tree for a given amount of leafs.
  *
@@ -11,20 +10,27 @@ * The construction rounds the amount of leafs up to the nearest two-power with
  */
-export function newBareTree(leafs: number): API.TreeData;
+export function allocate(leafs: number): PieceTree;
 export { computeNode } from "../proof.js";
-export function depth(tree: API.TreeData): number;
+export const MAX_LEAF_COUNT: number;
 export function root(tree: API.TreeData): API.MerkleTreeNode;
 export function split(source: Uint8Array): API.MerkleTreeNode[];
 export function build(source: API.Fr23Padded): API.PieceTree;
-export function buildFromChunks(chunks: API.MerkleTreeNode[]): API.PieceTree;
-export function buildFromLeafs(leafs: API.MerkleTreeNode[]): API.PieceTree;
+export function fromChunks(chunks: API.MerkleTreeNode[]): API.PieceTree;
+export function fromLeafs(leafs: API.MerkleTreeNode[]): API.PieceTree;
 export function padLeafs(leafs: API.MerkleTreeNode[]): API.MerkleTreeNode[];
-import * as API from '../api.js';
-declare class PieceTree {
+/**
+ * @implements {API.PieceTree}
+ */
+declare class PieceTree implements API.PieceTree {
     /**
-     * @param {API.TreeData} model
+     * @param {object} data
+     * @param {API.MerkleTreeNode[][]} data.nodes
+     * @param {number} data.height
      */
-    constructor(model: API.TreeData);
-    model: API.TreeData;
+    constructor({ nodes, height }: {
+        nodes: API.MerkleTreeNode[][];
+        height: number;
+    });
+    nodes: API.MerkleTreeNode[][];
+    height: number;
     get root(): API.MerkleTreeNode;
-    get depth(): number;
     get leafs(): API.MerkleTreeNode[];
@@ -39,2 +45,3 @@ get leafCount(): number;
 }
+import * as API from '../api.js';
 //# sourceMappingURL=tree.d.ts.map

dist/src/piece/unpadded-size.d.ts

 export function from(size: number | API.uint64): API.UnpaddedPieceSize;
 export function validate(size: API.uint64): API.Result<API.UnpaddedPieceSize, Error>;
 export function toPaddedSize(size: API.UnpaddedPieceSize): API.PaddedPieceSize;
+export function toHeight(size: API.UnpaddedPieceSize): number;
 import * as API from '../api.js';
 //# sourceMappingURL=unpadded-size.d.ts.map

package.json

 {
   "name": "@web3-storage/data-segment",
   "description": "Implementation of [FRC-0058](https://github.com/filecoin-project/FIPs/blob/master/FRCs/frc-0058.md) verifiable aggregation scheme",
-  "version": "2.0.0",
+  "version": "2.1.0",
   "keywords": [
@@ -6,0 +6,0 @@ "FRC-0058",

src/aggregate.js

@@ -12,3 +12,3 @@ import * as API from './api.js'
 const EntrySize = Number(Index.EntrySize)
-export const MAX_CAPACITY = 2n ** BigInt(Tree.MAX_LOG2_LEAFS) * NodeSize
+export const MAX_CAPACITY = 2n ** BigInt(Tree.MAX_HEIGHT) * NodeSize
 
@@ -152,3 +152,3 @@ /**
    */
-  estimate({ root, size }) {
+  estimate({ link, size }) {
     if (this.parts.length >= this.limit) {
@@ -188,3 +188,3 @@ return {
       ok: {
-        parts: [{ node: root, location: { level, index } }],
+        parts: [{ node: link.multihash.digest, location: { level, index } }],
         offset: offset - this.offset,
@@ -203,3 +203,3 @@ },
    * @param {number} source.limit
-   * @param {API.MerkleTree} source.tree
+   * @param {API.AggregateTree} source.tree
    */
@@ -212,2 +212,3 @@ constructor({ tree, parts, limit, size, offset }) {
     this.offset = offset
+    this.link = Piece.createLink(this.tree.root)
   }
@@ -220,15 +221,14 @@ /**
   }
-  link() {
-    return Piece.createLink(this.tree.root)
+  /**
+   * Height of the perfect binary merkle tree corresponding to this aggregate.
+   */
+  get height() {
+    return this.tree.height
   }
   toJSON() {
     return {
-      link: { '/': this.link().toString() },
-      // Note that currently our aggregate size is always 32GiB and that is
-      // below the `Number.MAX_SAFE_INTEGER` so we can safely convert it to
-      // a number.
-      // ⚠️ We must revisit this to support larger aggregates in the future.
-      size: Number(this.size),
+      link: { '/': this.link.toString() },
+      height: this.height,
     }
   }
 }

src/aggregate/tree.js

@@ -8,54 +8,53 @@ import * as API from '../api.js'
 /**
- * We allow up to 2 ** 60 leafs in the tree, with is greater than then
- * Number.MAX_SAFE_INTEGER ((2 ** 53) - 1) which is why we need to use
- * uint64s.
+ * We limit tree height to 60, since we have a perfect binary merkle tree this
+ * will fit up to 2 ** 60 of leafs nodes.
  */
-export const MAX_LOG2_LEAFS = 60
+export const MAX_HEIGHT = 60
 
 /**
- * @param {number} log2Leafs
+ * Creates a new tree with a given tree `height`.
+ *
+ * @param {number} height
  * @returns {API.AggregateTree}
  */
-export const create = (log2Leafs) => {
-  if (log2Leafs > MAX_LOG2_LEAFS) {
-    throw new RangeError(`too many leafs: 2 ** ${log2Leafs}`)
+export const create = (height) => {
+  if (height > MAX_HEIGHT) {
+    throw new RangeError(`too many leafs: 2 ** ${height}`)
   }
 
-  if (log2Leafs < 0) {
+  if (height < 0) {
     throw new RangeError(`cannot have negative log2Leafs`)
   }
 
-  return new AggregateTree(log2Leafs)
+  return new AggregateTree(height)
 }
 
+/**
+ * @implements {API.AggregateTree}
+ */
 class AggregateTree {
   /**
-   * The sparse array contains the data of the tree. Levels of the tree are
-   * counted from the leaf layer (layer 0).
-   * Where the leaf layer lands depends on the `log2Leafs` value.
-   * The root node of a the tree is stored at position [1].
-   *
-   * @param {number} log2Leafs
+   * @param {number} height
    * @param {SparseArray<API.MerkleTreeNode>} data
    */
 
-  constructor(log2Leafs, data = new SparseArray()) {
-    this.log2Leafs = log2Leafs
+  constructor(height, data = new SparseArray()) {
+    /**
+     * The sparse array contains the data of the tree. Levels of the tree are
+     * counted from the leaf layer (layer 0).
+     *
+     * Where the leaf layer lands depends on the `height` of the tree.
+     */
     this.data = data
+    this.height = height
   }
 
-  get maxLevel() {
-    return this.log2Leafs
-  }
-
   get leafCount() {
-    return 2n ** BigInt(this.log2Leafs)
+    // Since this is a perfect binary tree, the leaf count is 2 ** height, it
+    // is a bigint as it may exceed Number.MAX_SAFE_INTEGER (2 ** 53 - 1).
+    return 2n ** BigInt(this.height)
   }
 
-  get depth() {
-    return this.log2Leafs + 1
-  }
-
   get root() {
-    return this.node(this.maxLevel, 0n)
+    return this.node(this.height, 0n)
   }
@@ -71,7 +70,7 @@
   collectProof(level, index) {
-    validateLevelIndex(this.log2Leafs, level, index)
+    validateLevelIndex(this.height, level, index)
     const path = []
     let currentLevel = level
     let currentIndex = index
-    while (currentLevel < this.maxLevel) {
+    while (currentLevel < this.height) {
       // idx^1 is the sibling index
@@ -104,3 +103,3 @@ const node = this.node(currentLevel, currentIndex ^ 1n)
   setNode(level, index, node) {
-    validateLevelIndex(this.log2Leafs, level, index)
+    validateLevelIndex(this.height, level, index)
 
@@ -120,7 +119,7 @@ if (level > 0) {
 
-    this.data.set(idxFor(this.log2Leafs, level, index), node)
+    this.data.set(idxFor(this.height, level, index), node)
 
     let currentIndex = index
     let n = level
-    while (n < this.maxLevel) {
+    while (n < this.height) {
       const nextIndex = currentIndex >> 1n
@@ -141,3 +140,3 @@ // clear the lowest bit of index for left node
 
-      this.data.set(idxFor(this.log2Leafs, n + 1, nextIndex), node)
+      this.data.set(idxFor(this.height, n + 1, nextIndex), node)
       currentIndex = nextIndex
@@ -169,15 +168,17 @@ n++
  * @template T
+ * @implements {API.SparseArray<T>}
  */
 class SparseArray {
   /**
-   * @param {Map<API.uint64, T[]>} subs
+   * @param {Map<API.uint64, T[]>} shards
    */
-  constructor(subs = new Map()) {
+  constructor(shards = new Map()) {
     /**
      * @private
      */
-    this.subs = subs
+    this.shards = shards
   }
   clear() {
-    this.subs.clear()
+    this.shards.clear()
+    return this
   }
@@ -190,3 +191,3 @@ /**
     const subIndex = index / BigIntSparseBlockSize
-    const sub = this.subs.get(subIndex)
+    const sub = this.shards.get(subIndex)
     if (!sub) {
@@ -204,9 +205,11 @@ return undefined
     const subIndex = index / BigIntSparseBlockSize
-    let sub = this.subs.get(subIndex)
-    if (!sub) {
-      sub = new Array(SparseBlockSize)
-      this.subs.set(subIndex, sub)
+    let shard = this.shards.get(subIndex)
+    if (!shard) {
+      shard = new Array(SparseBlockSize)
+      this.shards.set(subIndex, shard)
     }
 
-    sub[Number(index % BigIntSparseBlockSize)] = value
+    shard[Number(index % BigIntSparseBlockSize)] = value
+
+    return this
   }
@@ -222,15 +225,15 @@
   slice(start, end) {
-    const startSub = start / BigIntSparseBlockSize
-    const endSub = (end - 1n) / BigIntSparseBlockSize
-    if (startSub !== endSub) {
+    const startShard = start / BigIntSparseBlockSize
+    const endShard = (end - 1n) / BigIntSparseBlockSize
+    if (startShard !== endShard) {
       throw new Error('requested slice does not align with one sparse block')
     }
 
-    let sub = this.subs.get(startSub)
-    if (!sub) {
-      sub = new Array(SparseBlockSize)
-      this.subs.set(startSub, sub)
+    let shard = this.shards.get(startShard)
+    if (!shard) {
+      shard = new Array(SparseBlockSize)
+      this.shards.set(startShard, shard)
     }
 
-    return sub.slice(
+    return shard.slice(
       Number(start % BigIntSparseBlockSize),
@@ -264,3 +267,3 @@ Number(end % BigIntSparseBlockSize)
  * @typedef {{
- * log2Leafs: number
+ * height: number
  * data: SparseArray<API.MerkleTreeNode>
@@ -274,5 +277,5 @@ * }} Model
 const getNodeRaw = (tree, level, idx) => {
-  validateLevelIndex(tree.log2Leafs, level, idx)
+  validateLevelIndex(tree.height, level, idx)
 
-  return tree.data.at(idxFor(tree.log2Leafs, level, idx))
+  return tree.data.at(idxFor(tree.height, level, idx))
 }
@@ -304,3 +307,3 @@
 /**
- * @param {number} maxLevel
+ * @param {number} height
  * @param {number} level
@@ -310,4 +313,4 @@ * @param {API.uint64} index
  */
-export const idxFor = (maxLevel, level, index) => {
-  const depth = maxLevel - level
+export const idxFor = (height, level, index) => {
+  const depth = height - level
   // Hybrid Tree stores the MT as smaller trees in chunks dictated by SparseBlockSize
@@ -314,0 +317,0 @@ // For example with SparseBlockLog2Size of 8, each SparseBlock will store a single

src/api.ts

@@ -0,3 +1,5 @@
+import exp from 'constants'
 import type { Link, ToString } from 'multiformats/link'
 
+export { ToString }
 /**
@@ -53,8 +55,2 @@ * Implementers of the `Read` interface are called "readers". Readers
 
-export interface AggregateState {
-  capacity: number
-  offset: number
-  parts: MerkleTreeNodeSource[]
-}
-
 export interface Vector<T> extends Iterable<T> {
@@ -82,10 +78,11 @@ append(value: T): Vector<T>
   /**
-   * The Depth of the tree. A single-node tree has depth of 1
-   */
-  depth: number
-  /**
    * Amount of leafs in this Merkle tree.
    */
   leafCount: I
+
   /**
+   * Height of the tree.
+   */
+  height: number
+  /**
    * Root node of this Merkle tree.
@@ -118,6 +115,6 @@ */
 
-export interface AggregateTree
-  extends MerkleTree<uint64>,
-    MerkleTreeBuilder<uint64> {
-  collectProof(level: number, index: uint64): ProofData
+export interface AggregateTree<I extends uint64 | number = uint64>
+  extends MerkleTree<I>,
+    MerkleTreeBuilder<I> {
+  collectProof(level: number, index: I): ProofData
 }
@@ -130,3 +127,3 @@
    */
-  root: MerkleTreeNode
+  link: PieceLink
 
@@ -139,22 +136,37 @@ /**
 
-export interface Piece extends PieceInfo {
-  link(): PieceLink
-  toJSON(): {
-    link: { '/': string }
-    size: number
-  }
+export interface PieceInfoView extends PieceInfo {
+  /**
+   * Height of the perfect binary merkle tree representing
+   * this piece.
+   */
+  height: number
 }
 
-export interface ContentPiece extends Piece {
+/**
+ * Represents a piece tree and underlying merkle tree.
+ */
+export interface Piece extends PieceInfoView {
+  tree: PieceTree
+
+  /**
+   * Size of the payload from which this piece was derived.
+   */
   contentSize: number
+
+  /**
+   * Size after 0 padding to next power of 2.
+   */
   paddedSize: number
 
-  toJSON(): {
-    link: { '/': string }
-    contentSize: number
-    paddedSize: number
-    size: number
-  }
+  /**
+   * Returns a JSON representation of this piece.
+   */
+  toJSON(): PieceJSON
 }
 
+export interface PieceJSON {
+  link: { '/': string }
+  height: number
+}
+
 export type PieceLink = Link<MerkleTreeNode, 0xf101, 0x1012>
@@ -248,2 +260,3 @@
   nodes: MerkleTreeNode[][]
+
   /**
@@ -253,5 +266,24 @@ * Leafs is the amount of raw leafs being used. I.e. without padding to
    */
-  leafs: number
+  height: number
 }
 
+export interface AggregateTreeData {
+  /**
+   * Height of the (perfect binary) tree.
+   */
+  height: number
+
+  /**
+   * Sparse array that contains tree nodes. Levels
+   * of the tree are counted from the leaf layer (0).
+   */
+  data: SparseArray<MerkleTreeNode>
+}
+
+export interface SparseArray<T> {
+  clear(): this
+  at(index: uint64): T | undefined
+  set(index: uint64, value: T): this
+}
+
 export interface ProofData {
@@ -258,0 +290,0 @@ path: MerkleTreeNode[]

src/fr32.js

@@ -50,8 +50,8 @@ import * as API from './api.js'
   const size = Math.max(sourceSize, MIN_PIECE_SIZE)
-  let highestBit = Math.floor(Math.log2(size))
+  const highestBit = Math.floor(Math.log2(size))
 
-  const bound = Math.ceil(FR_RATIO * (1 << (highestBit + 1)))
+  const bound = Math.ceil(FR_RATIO * 2 ** (highestBit + 1))
   // the size is either the closest pow2 number, or the next pow2 number if we
   // don't have space for padding
-  return size <= bound ? bound : Math.ceil(FR_RATIO * (1 << (highestBit + 2)))
+  return size <= bound ? bound : Math.ceil(FR_RATIO * 2 ** (highestBit + 2))
 }
@@ -58,0 +58,0 @@

src/piece.js

@@ -9,2 +9,3 @@ import * as API from './api.js'
 import * as PaddedSize from './piece/padded-size.js'
+import { log2Ceil } from './uint64.js'
 
@@ -24,52 +25,87 @@ export { Tree }
 /**
- * MaxLayers is the current maximum height of the rust-fil-proofs proving tree.
+ * Current maximum piece size is limited by the maximum number of leaves in the
+ * tree, which is limited by max size of the JS array, which is 128GiB.
  */
-export const MAX_LAYERS = 31 // result of log2( 64 GiB / 32 )
+export const MAX_PIECE_SIZE = Tree.MAX_LEAF_COUNT * NodeSize
 
 /**
- * Current maximum size of the rust-fil-proofs proving tree.
+ * The maximum amount of data that one can compute for the piece.
  */
-export const MAX_PIECE_SIZE = 1 << (MAX_LAYERS + 5)
+export const MAX_PAYLOAD_SIZE = (MAX_PIECE_SIZE / 128) * 127
 
+export { UnpaddedSize, PaddedSize }
+
 /**
- * MaxPiecePayload is the maximum amount of data that one can compute commP for.
- * Constrained by the value of {@link MAX_LAYERS}.
+ * @param {API.PieceInfo} piece
  */
-export const MAX_PIECE_PAYLOAD = (MAX_PIECE_SIZE / 128) * 127
+class PieceInfo {
+  /**
+   * @param {object} data
+   * @param {API.PieceLink} data.link
+   * @param {number} data.height
+   */
+  constructor({ link, height }) {
+    this.link = link
+    this.height = height
+  }
+  get size() {
+    return 2n ** BigInt(this.height) * BigInt(NodeSize)
+  }
+  toJSON() {
+    return toJSON(this)
+  }
+  toString() {
+    return toString(this)
+  }
+}
 
-export { UnpaddedSize, PaddedSize }
-
-class Piece {
+/**
+ * @implements {API.Piece}
+ */
+class Piece extends PieceInfo {
   /**
    * @param {object} data
-   * @param {number} data.size
-   * @param {API.MerkleTree} data.tree
+   * @param {number} data.contentSize
+   * @param {API.PieceTree} data.tree
    */
-  constructor({ size, tree }) {
-    this.contentSize = size
+  constructor({ contentSize, tree }) {
+    super({ link: createLink(tree.root), height: tree.height })
+    this.contentSize = contentSize
     this.tree = tree
   }
-  get root() {
-    return this.tree.root
-  }
+
   get paddedSize() {
     return Fr32.toZeroPaddedSize(this.contentSize)
   }
-  get size() {
-    return BigInt(this.tree.leafCount) * BigInt(NodeSize)
-  }
-  link() {
-    return createLink(this.tree.root)
-  }
-  toJSON() {
-    return {
-      link: { '/': this.link().toString() },
-      contentSize: this.contentSize,
-      paddedSize: this.paddedSize,
-      size: Number(this.size),
-    }
-  }
 }
 
 /**
+ * @param {API.PieceInfo} piece
+ * @returns {API.PieceJSON}
+ */
+export const toJSON = (piece) => ({
+  link: { '/': piece.link.toString() },
+  height: PaddedSize.toHeight(piece.size),
+})
+
+/**
+ *
+ * @param {API.PieceJSON} json
+ * @returns {API.PieceInfoView}
+ */
+export const fromJSON = ({ link, height }) =>
+  new PieceInfo({ link: Link.parse(link['/']), height })
+
+/**
+ * @param {API.PieceInfo} piece
+ * @returns {API.ToString<API.PieceJSON>}
+ */
+export const toString = (piece) => JSON.stringify(toJSON(piece), null, 2)
+
+/**
+ * @param {API.ToString<API.PieceJSON>|string} source
+ */
+export const fromString = (source) => fromJSON(JSON.parse(source))
+
+/**
  * Creates Piece CID from the the merkle tree root. It will not perform
@@ -89,14 +125,20 @@ * any validation.
  * @param {Uint8Array} source
- * @returns {API.ContentPiece}
+ * @returns {API.Piece}
  */
 export const build = (source) => {
-  if (source.byteLength < Fr32.MIN_PIECE_SIZE) {
+  if (source.length < Fr32.MIN_PIECE_SIZE) {
     throw new RangeError(
-      `commP is not defined for inputs shorter than ${Fr32.MIN_PIECE_SIZE} bytes`
+      `Piece is not defined for payloads smaller than ${Fr32.MIN_PIECE_SIZE} bytes`
     )
   }
 
+  if (source.length > MAX_PAYLOAD_SIZE) {
+    throw new RangeError(
+      `Payload exceeds maximum supported size of ${MAX_PAYLOAD_SIZE} bytes`
+    )
+  }
+
   const tree = Tree.build(Fr32.pad(source))
 
-  return new Piece({ tree, size: source.byteLength })
+  return new Piece({ tree, contentSize: source.byteLength })
 }

src/piece/padded-size.js

 import * as API from '../api.js'
-import { onesCount64 } from '../uint64.js'
+import { onesCount64, log2Ceil } from '../uint64.js'
+import * as Node from '../node.js'
 
+const NODE_SIZE = BigInt(Node.Size)
+
 /**
@@ -51,1 +54,8 @@ * Validates that given `size` is a valid {@link API.PaddedPieceSize} and
 export const toUnpaddedSize = (size) => size - size / 128n
+
+/**
+ * Calculates the height of the piece tree from unpadded size.
+ *
+ * @param {API.PaddedPieceSize} size
+ */
+export const toHeight = (size) => log2Ceil(size / NODE_SIZE)

src/piece/tree.js

@@ -6,5 +6,9 @@ import * as API from '../api.js'
 
+// The value is an unsigned, 32-bit integer that is always numerically greater
+// than the highest index in the array. This means our tree can represent a
+// piece up to 128 GiB in size.
+export const MAX_LEAF_COUNT = 2 ** 32 - 1
+
 /**
- * `newBareTree` allocates that memory needed to construct a tree with a
- * specific amount of leafs.
+ * Allocates a tree for a given amount of leafs.
  *
@@ -17,15 +21,19 @@ * The construction rounds the amount of leafs up to the nearest two-power with
  */
-export function newBareTree(leafs) {
-  const adjustedLeafs = 1 << Math.ceil(Math.log2(leafs))
-  /** @type {API.TreeData} */
-  const tree = {
-    nodes: new Array(Math.ceil(Math.log2(adjustedLeafs)) + 1),
-    leafs: leafs,
+export function allocate(leafs) {
+  const adjustedLeafs = 2 ** Math.ceil(Math.log2(leafs))
+
+  if (adjustedLeafs > MAX_LEAF_COUNT) {
+    throw new RangeError(
+      `too many leafs ${adjustedLeafs} exceeds ${MAX_LEAF_COUNT} limit`
+    )
   }
 
-  for (const level of tree.nodes.keys()) {
-    tree.nodes[level] = new Array(1 << level)
+  const height = Math.ceil(Math.log2(adjustedLeafs))
+  const nodes = new Array(height + 1)
+
+  for (const level of nodes.keys()) {
+    nodes[level] = new Array(1 << level)
   }
 
-  return tree
+  return new PieceTree({ nodes, height })
 }
@@ -36,3 +44,3 @@
  */
-export const depth = (tree) => {
+const depth = (tree) => {
   return tree.nodes.length
@@ -68,3 +76,3 @@ }
  */
-export const build = (source) => buildFromChunks(split(source))
+export const build = (source) => fromChunks(split(source))
 
@@ -74,3 +82,3 @@ /**
  */
-export const buildFromChunks = (chunks) => {
+export const fromChunks = (chunks) => {
   if (chunks.length === 0) {
@@ -81,3 +89,3 @@ throw new RangeError('Empty source')
   const leafs = chunks //await Promise.all(chunks.map(truncatedHash))
-  return buildFromLeafs(leafs)
+  return fromLeafs(leafs)
 }
@@ -89,4 +97,4 @@
  */
-export const buildFromLeafs = (leafs) => {
-  const tree = newBareTree(leafs.length)
+export const fromLeafs = (leafs) => {
+  const tree = allocate(leafs.length)
   // Set the padded leaf nodes
@@ -126,22 +134,25 @@ tree.nodes[depth(tree) - 1] = padLeafs(leafs)
 
+/**
+ * @implements {API.PieceTree}
+ */
 class PieceTree {
   /**
-   * @param {API.TreeData} model
+   * @param {object} data
+   * @param {API.MerkleTreeNode[][]} data.nodes
+   * @param {number} data.height
    */
-  constructor(model) {
-    this.model = model
+  constructor({ nodes, height }) {
+    this.nodes = nodes
+    this.height = height
   }
 
   get root() {
-    return root(this.model)
+    return root(this)
   }
-  get depth() {
-    return depth(this.model)
-  }
   get leafs() {
-    const { nodes } = this.model
+    const { nodes } = this
     return nodes[nodes.length - 1]
   }
   get leafCount() {
-    return this.model.leafs
+    return 2 ** this.height
   }
@@ -154,5 +165,5 @@ /**
   node(level, index) {
-    const { nodes } = this.model
+    const { nodes } = this
     return nodes[level][index]
   }
 }

src/piece/unpadded-size.js

 import * as API from '../api.js'
-import { trailingZeros64 } from '../uint64.js'
+import { trailingZeros64, log2Ceil } from '../uint64.js'
+import * as Node from '../node.js'
 
+const NODE_SIZE = BigInt(Node.Size)
+
 /**
@@ -63,1 +66,8 @@ * Validates that given `size` is a valid {@link API.UnpaddedPieceSize} and
 export const toPaddedSize = (size) => size + size / 127n
+
+/**
+ * Calculates the height of the piece tree from unpadded size.
+ *
+ * @param {API.UnpaddedPieceSize} size
+ */
+export const toHeight = (size) => log2Ceil(toPaddedSize(size) / NODE_SIZE)

No alert changes

Improved metrics

Total package byte prevSize

93116

increased by6.04%

Lines of code

2533

increased by6.79%

No dependency changes