Skip to main content

Data Inclusion Proof

💜 Support the DIG Network

Help build the future of decentralized storage! The DIG Network is an open-source project that needs community support to continue development.

💜 Support the Project → - Donate crypto, buy NFTs, or sponsor development

Overview​

The Data Inclusion Proof is a standard merkle proof demonstrating that a specific capsule hash exists within a plot's merkle tree. Since the merkle root is public from the plot ownership proof, plain merkle proofs provide optimal efficiency.

Mechanism​

Standard Merkle Proof​

interface DataInclusionProof {
    leafIndex: uint32;        // Position in tree
    leafHash: bytes32;        // H(capsule)
    siblings: bytes32[];      // Merkle path
    directions: boolean[];    // Left/right flags
}

Tree Construction​

def build_plot_merkle_tree(capsule_hashes):
    # Sort for deterministic ordering
    sorted_hashes = sorted(capsule_hashes)
    
    # Pad to power of 2
    tree_size = next_power_of_2(len(sorted_hashes))
    leaves = sorted_hashes + [EMPTY_HASH] * (tree_size - len(sorted_hashes))
    
    # Build tree bottom-up
    return construct_merkle_tree(leaves)

Generation​

Proof Creation​

def generate_data_inclusion_proof(plot, capsule_id):
    # Get merkle proof from plot structure
    merkle_proof = plot.get_merkle_proof(capsule_id)
    
    return DataInclusionProof(
        leafIndex=merkle_proof.index,
        leafHash=sha256(capsule_id),
        siblings=merkle_proof.siblings,
        directions=merkle_proof.directions
    )

Verification​

def verify_data_inclusion(proof, capsule_hash, expected_merkle_root):
    # Verify leaf hash matches
    if proof.leafHash != capsule_hash:
        return False
    
    # Compute merkle root
    current_hash = capsule_hash
    
    for sibling, is_left in zip(proof.siblings, proof.directions):
        if is_left:
            current_hash = sha256(current_hash + sibling)
        else:
            current_hash = sha256(sibling + current_hash)
    
    return current_hash == expected_merkle_root

Information Disclosure​

What's Revealed​

Plain merkle proofs expose:

  • Tree depth (reveals plot size class)
  • Capsule position (leaf index)
  • Sibling hashes along path

Privacy Analysis​

def information_leakage(proof):
    return {
        'plot_size_class': 2**len(proof.siblings),
        'capsule_count_range': estimate_count_from_depth(len(proof.siblings)),
        'partial_structure': len(proof.siblings) * 32  # bytes
    }

Why It's Acceptable​

  1. Limited Value: Tree structure isn't sensitive
  2. Already Public: Plot size typically known
  3. No Content: Only hashes revealed

Performance​

Proof Size​

def calculate_proof_size(tree_depth):
    return {
        'leaf_index': 4,           # bytes
        'leaf_hash': 32,           # bytes
        'siblings': tree_depth * 32,  # bytes
        'directions': tree_depth,     # bits
        'total': 36 + (tree_depth * 33)  # bytes
    }

Example Sizes​

Plot SizeTree DepthProof Size
1K capsules10366 bytes
1M capsules20696 bytes
1B capsules301026 bytes

Integration​

In Proof Package​

ProofPackage = {
    'plotOwnership': {
        'merkleRoot': plot.root,  # Public commitment
        'signature': bls_signature
    },
    'dataInclusion': {
        'leafIndex': index,
        'siblings': path,         # Plain merkle proof
        'directions': dirs
    },
    'computationalWork': proof_of_work,
    'physicalAccess': {
        'blockHeight': height,
        'chunkData': chunks,
        'chunkProofs': proofs
    }
}

Verification Flow​

def verify_complete_package(package):
    # Step 1: Get trusted merkle root
    merkle_root = package.plotOwnership.merkleRoot
    
    # Step 2: Verify ownership signature
    if not verify_bls_signature(package.plotOwnership):
        return False
    
    # Step 3: Verify capsule inclusion
    if not verify_data_inclusion(
        package.dataInclusion,
        package.capsuleHash,
        merkle_root
    ):
        return False
    
    # Continue with other proofs...
    return True

Design Rationale​

Why Not Zero-Knowledge?​

  1. Performance: 10x faster verification
  2. Size: 100x smaller proofs
  3. Simplicity: Standard implementation
  4. Low Risk: Structure not sensitive

Security Properties​

  • Soundness: Cannot forge membership
  • Completeness: Valid proofs always verify
  • Binding: Tied to plot ownership proof
  • Non-malleability: Unique proof per capsule

Optimization​

Batch Verification​

def verify_multiple_inclusions(proofs, capsule_hashes, merkle_root):
    # Share computation for common paths
    path_cache = {}
    
    for proof, capsule_hash in zip(proofs, capsule_hashes):
        if not verify_with_cache(proof, capsule_hash, merkle_root, path_cache):
            return False
    
    return True

Proof Compression​

def compress_inclusion_proofs(proofs):
    # Delta encode indices
    # Share common siblings
    # Bit-pack directions
    return compressed_format

Summary​

The Data Inclusion Proof leverages the public merkle root from plot ownership to enable efficient capsule existence verification. Plain merkle proofs provide optimal performance while maintaining cryptographic security. The minimal information disclosure is an acceptable tradeoff for the significant efficiency gains in the DIG Network's high-throughput validation system.