Comprehensive Explanation

percolated-discovery

Process Definition

Percolated discovery (also known as Percolated Information Discovery or PID) is a discovery mechanism integrated into the OOBI (Out-Of-Band Introduction) protocol that serves both KERI and ACDC ecosystems. The process enables the discovery of IP resources (service endpoints) associated with Autonomic Identifiers (AIDs) or Self-Addressing Identifiers (SAIDs) through a mathematically-grounded approach based on Invasion Percolation Theory.

The fundamental innovation of percolated discovery is that it transforms discovery from a security problem into an availability problem. Because all discovered information is end-verifiable, the discovery path itself does not need to be trusted. This enables what is termed zero-trust percolated discovery or speedy percolated discovery.

What It Accomplishes

Percolated discovery accomplishes several critical objectives:

1. Decentralized endpoint discovery: Enables discovery of witness endpoints, watcher networks, and other KERI infrastructure without centralized directories
2. Scalable information propagation: After initial bootstrap via OOBI, subsequent authorization becomes non-interactive, creating highly scalable discovery
3. Zero-trust architecture: Eliminates the need to trust discovery intermediaries or the percolation mechanism itself
4. Privacy-preserving options: Supports both public and private discovery topologies based on user permissions
5. Resilient infrastructure: Creates naturally redundant discovery paths following principles of least resistance

When It's Used

Percolated discovery is employed in several key scenarios:

• Initial bootstrap: When a validator first encounters an AID and needs to discover its witness pool
• Infrastructure discovery: When locating watchers, registrars, or other KERI components
• Credential verification: When a verifier needs to discover the infrastructure supporting an ACDC issuer
• Network expansion: As new nodes join the KERI ecosystem and need to discover existing infrastructure
• Recovery scenarios: When primary discovery paths fail and alternative routes are needed

Key Participants

The percolated discovery process involves several participant roles:

1. Discoverers: Entities seeking to discover information about AIDs or infrastructure endpoints
2. Sharers: Entities that have already discovered information and share it with subsequent discoverers
3. Controllers: AID controllers who initially publish OOBIs for their infrastructure
4. Witnesses: Infrastructure components whose endpoints are being discovered
5. Watchers: Super-nodes that aggregate discovery information for enhanced availability

Process Flow

Step 1: Bootstrap via OOBI

The percolated discovery process begins with an Out-Of-Band Introduction (OOBI). An OOBI is a simple association between a URL and an AID, which can be as minimal as:

http://8.8.5.6:8080/oobi/EaU6JR2nmwyZ-i0d8JZAoTNZH3ULvYAfSVPzhzS6b5CM

This initial OOBI can be obtained through various out-of-band channels:

• QR codes
• Email or messaging
• Web pages or social media
• DNS records (used only for discovery, not authentication)
• Direct communication

The critical property is that the OOBI itself is not trusted. It merely provides a starting point for discovery.

Step 2: Initial Discovery and Verification

Once a discoverer obtains an OOBI, they:

1. Resolve the URL to retrieve discovery information (typically a KEL or KERL)
2. Cryptographically verify the retrieved information using KERI's end-verifiable properties
3. Extract additional discovery information such as:
   • Witness endpoints
   • Watcher locations
   • Registry identifiers
   • Service endpoints

The verification process ensures that even if the OOBI source was malicious or the URL was compromised, the discoverer can detect any tampering through cryptographic validation.

Step 3: Percolation (Transitive Sharing)

The defining characteristic of percolated discovery is that each discoverer becomes a potential sharer. Once a discoverer has verified information about an AID, they can:

1. Share their discovery with other entities seeking the same information
2. Provide OOBIs pointing to their own endpoints where the verified information is available
3. Act as a percolation node in the discovery network

This creates a connected cluster of nodes that have discovered and can verify the information, analogous to how fluid percolates through porous media in the physical model.

Step 4: Least Resistance Path Selection

Following the Invasion Percolation model, information naturally flows through paths of least resistance:

• Popular endpoints become natural discovery hubs
• Well-connected nodes facilitate faster percolation
• Geographically proximate or network-proximate nodes may be preferred
• Trusted relationships (in user-permissioned networks) create preferred paths

The system does not require explicit routing or path selection algorithms—the percolation naturally optimizes for efficient discovery paths based on the network topology and node accessibility.

Step 5: Non-Interactive Authorization

After the initial bootstrap, subsequent authorization becomes non-interactive. This means:

1. No challenge-response required: Discoverers can verify information without interacting with the original source
2. Cached information is verifiable: Previously discovered information remains cryptographically valid
3. Offline verification possible: Discovery information can be verified without network connectivity to original sources
4. Scalability achieved: The system scales horizontally as more nodes participate in percolation

State Changes During Discovery

The discovery process involves several state transitions:

Initial State: Discoverer has only an AID or SAID with no endpoint information

Bootstrap State: Discoverer has obtained an OOBI but has not yet verified it

Verified State: Discoverer has cryptographically verified the discovered information and can now use it

Sharer State: Discoverer can now act as a percolation node, sharing verified information with subsequent discoverers

Cached State: Discoverer maintains verified information for future use and sharing

Decision Points

Several decision points exist in the percolation process:

1. Trust the OOBI source?: While the OOBI itself is not trusted cryptographically, discoverers may choose to prioritize OOBIs from known sources
2. Which percolation path?: When multiple discovery paths exist, discoverers may select based on latency, trust relationships, or other criteria
3. Share discoveries?: Discoverers decide whether to participate in percolation by sharing their discoveries
4. Public vs. private discovery?: Controllers decide whether to enable public discovery or restrict to permissioned networks
5. Cache duration?: Discoverers determine how long to cache verified discovery information

Technical Requirements

Cryptographic Requirements

Percolated discovery relies on several cryptographic properties:

End-Verifiability

All discovered information must be end-verifiable, meaning:

• Self-certifying identifiers: AIDs are cryptographically bound to their controlling key pairs
• Signed key events: All key events in a KEL are signed by authoritative keys
• Hash chaining: Events are linked through cryptographic digests
• Witness receipts: Witnesses provide signed receipts of events they observe

These properties ensure that discoverers can verify information authenticity without trusting the discovery path.

SAID Protocol

Discovered data structures use SAIDs (Self-Addressing Identifiers) to provide:

• Content-addressable references: SAIDs uniquely identify content through cryptographic binding
• Integrity verification: Any modification to content invalidates the SAID
• Compact representation: SAIDs enable compact disclosure while maintaining verifiable commitments

Digital Signatures

All authoritative statements in discovered information must be:

• Signed by current keys: Using keys from the current key state
• Non-repudiable: Signatures provide proof of authorship
• Verifiable: Using public keys from the KEL

Timing Considerations

Bootstrap Latency

The initial bootstrap via OOBI may involve:

• Network round-trips: To resolve URLs and retrieve discovery information
• Cryptographic verification: Computing and verifying digests and signatures
• KEL validation: Verifying the entire key event log from inception

Typical bootstrap latency ranges from milliseconds (for cached information) to seconds (for full KEL verification).

Percolation Propagation

Information percolation through the network follows eventual consistency principles:

• No guaranteed propagation time: Information spreads based on network topology and node behavior
• Faster for popular endpoints: Well-connected infrastructure percolates more quickly
• User-permissioned networks: May have slower percolation due to restricted sharing

Freshness vs. Availability Trade-off

Percolated discovery balances:

• Freshness: How recently the discovered information was verified
• Availability: How quickly information can be discovered

Cached information provides high availability but may be stale. The BADA (Best-Available-Data-Acceptance) policy helps manage this trade-off.

Error Handling

Invalid OOBI

When an OOBI resolves to invalid or unverifiable information:

1. Reject the discovery: Do not accept unverifiable information
2. Try alternative paths: Seek other OOBIs or percolation sources
3. Report to user: Indicate discovery failure
4. Do not propagate: Do not share invalid information

Duplicity Detection

If discovered information reveals duplicity (conflicting versions of a KEL):

1. Flag as duplicitous: Mark the AID as potentially compromised
2. Collect evidence: Gather both conflicting versions
3. Escalate to user: Allow user/policy decision on how to proceed
4. Do not auto-resolve: KERI does not automatically resolve duplicity

Network Failures

When network connectivity fails during discovery:

1. Use cached information: If available and within acceptable freshness bounds
2. Retry with backoff: Attempt discovery again with exponential backoff
3. Try alternative sources: Use different percolation paths
4. Degrade gracefully: Provide partial functionality with available information

Malicious Percolation Nodes

Because information is end-verifiable, malicious percolation nodes:

• Cannot forge information: Cryptographic verification detects tampering
• Can only deny service: By refusing to share or providing incorrect URLs
• Are naturally isolated: Honest nodes bypass them through alternative paths

The system is resilient to malicious percolation nodes because trust is not required.

Usage Patterns

Typical Scenarios

Scenario 1: Credential Verification

A verifier receives an ACDC credential and needs to verify the issuer:

1. Extract issuer AID: From the credential's i field
2. Obtain OOBI: From the credential metadata, QR code, or other source
3. Discover issuer KEL: Resolve OOBI to retrieve the KEL
4. Verify KEL: Validate signatures, hash chains, and witness receipts
5. Discover registry: Use discovered information to locate the TEL registry
6. Verify credential status: Check issuance/revocation status in registry

The entire process uses percolated discovery to locate necessary infrastructure without centralized directories.

Scenario 2: Witness Pool Discovery

A new validator encounters an AID and needs to discover its witness pool:

1. Receive AID: From a credential, message, or other source
2. Obtain witness OOBI: From the AID controller or percolation network
3. Discover witness endpoints: Resolve OOBI to get witness URLs
4. Query witnesses: Request KERL from multiple witnesses
5. Verify consistency: Ensure witnesses provide consistent key state
6. Cache witness information: Store for future use and potential sharing

Scenario 3: Watcher Network Integration

A watcher joins the network and needs to discover other watchers:

1. Bootstrap from known watchers: Use OOBIs for established watchers
2. Discover watcher network: Retrieve lists of other watchers
3. Establish connections: Connect to discovered watchers
4. Share discoveries: Provide OOBIs for own endpoints
5. Participate in percolation: Act as super-node for aggregated discovery

Watchers enhance percolation by serving as highly-available discovery hubs.

Best Practices

For Controllers (Information Publishers)

1. Publish multiple OOBIs: Provide OOBIs through diverse channels for redundancy
2. Use well-known paths: Leverage /.well-known/keri/oobi/ for discoverability
3. Maintain witness availability: Ensure witnesses are accessible for discovery
4. Consider privacy needs: Choose between public and private discovery based on requirements
5. Update OOBIs on rotation: When rotating infrastructure, publish new OOBIs

For Discoverers (Information Consumers)

1. Verify everything: Never trust discovery information without cryptographic verification
2. Use multiple sources: Obtain OOBIs from diverse sources when possible
3. Cache verified information: Reduce discovery latency by caching verified data
4. Participate in percolation: Share discoveries to strengthen the network
5. Implement BADA policy: Use Best-Available-Data-Acceptance for freshness management
6. Handle duplicity gracefully: Have policies for responding to detected duplicity

For Infrastructure Operators

1. Provide stable endpoints: Minimize endpoint changes to reduce discovery churn
2. Support standard OOBI formats: Implement well-known paths and query parameters
3. Enable CORS appropriately: Allow web-based discoverers to access endpoints
4. Monitor discovery patterns: Track discovery requests to optimize infrastructure
5. Participate as percolation nodes: Share discovery information to enhance network resilience

Integration Considerations

With KERI Protocol

Percolated discovery is deeply integrated with KERI:

• KEL discovery: Primary use case is discovering KELs for AIDs
• Witness discovery: Locating witness endpoints for KERL retrieval
• Watcher integration: Watchers serve as percolation super-nodes
• Delegation chains: Discovering delegated identifiers through parent AIDs

With ACDC Protocol

For ACDC credentials:

• Issuer discovery: Locating issuer infrastructure for verification
• Registry discovery: Finding TEL registries for status checking
• Schema discovery: Retrieving JSON Schema definitions via SAIDs
• Edge traversal: Following edges in credential chains through discovery

With OOBI Protocol

OOBI is the bootstrap mechanism for percolated discovery:

• OOBI variants: Support for bare, verbose, multi-OOBI, and blind OOBI formats
• Well-known paths: Standard URL patterns for predictable discovery
• Role specification: Query parameters indicating endpoint roles (witness, watcher, etc.)
• Recursive discovery: OOBIs can reference other OOBIs for multi-hop discovery

With DNS and Web Infrastructure

Percolated discovery leverages existing internet infrastructure safely:

• DNS for discovery only: DNS resolves URLs but does not provide authentication
• TLS optional: HTTPS provides transport security but is not required for verification
• Web search integration: OOBIs can be published on web pages for search engine discovery
• QR code encoding: OOBIs are compact enough for QR code representation

The key principle is "use but don't trust": existing infrastructure provides availability, while KERI provides security.

Mathematical Foundation: Invasion Percolation Theory

Percolation Theory Basics

Percolation theory is a mathematical framework for studying connected clusters in random systems. Originally developed to model fluid flow through porous media, it has applications across physics, mathematics, computer science, and social sciences.

Key concepts:

• Sites and bonds: Network nodes (sites) connected by links (bonds)
• Occupation probability: Likelihood that a site or bond is "open" (permeable)
• Percolation threshold: Critical occupation probability where a spanning cluster forms
• Connected clusters: Groups of occupied sites connected through open bonds

Invasion Percolation Model

Invasion percolation is a variant that models how fluids infiltrate porous media. The process follows the principle of least resistance:

1. Initial invasion: Fluid enters at a source site
2. Neighbor evaluation: Examine all dry neighbors of invaded sites
3. Minimum resistance selection: Invade the neighbor with lowest resistance
4. Cluster growth: Add newly invaded site to the connected cluster
5. Iteration: Repeat until desired coverage achieved

This creates a connected cluster of invaded sites that grows by progressively adding sites through paths of minimum resistance.

Application to Information Discovery

In percolated discovery, the invasion percolation model maps to information propagation:

• Invaded sites: Nodes that have discovered and verified information
• Dry sites: Nodes that have not yet discovered the information
• Resistance: Barriers to discovery (network latency, access restrictions, etc.)
• Invasion process: Information spreading through the network
• Connected cluster: Set of nodes that can verify and share the information

Least resistance paths emerge naturally:

• Popular endpoints have low resistance (high availability)
• Well-connected nodes facilitate faster percolation
• Trusted relationships (in permissioned networks) reduce resistance
• Geographic/network proximity lowers latency resistance

Percolation Verifiability

The critical property that enables secure percolation is end-verifiability. Each node in the percolation cluster can:

1. Verify information authenticity: Using cryptographic signatures and hash chains
2. Share verified information: Act as a percolation source for subsequent discoverers
3. Maintain security: Without trusting the percolation path or intermediaries

This transforms discovery from a security problem (requiring trusted paths) into an availability problem (finding any path to verified information).

Network Effects

Percolated discovery exhibits positive network effects:

• More discoverers: Increase percolation speed and redundancy
• More sharers: Create more discovery paths and resilience
• Natural optimization: Popular endpoints become discovery hubs
• Self-healing: Alternative paths emerge when primary paths fail

The system scales horizontally as the network grows, with no centralized bottlenecks.

Comparison with Alternative Discovery Mechanisms

Centralized Directories

Traditional systems use centralized directories (DNS, LDAP, etc.):

Advantages of centralized:

• Predictable lookup
• Consistent results
• Simple implementation

Disadvantages of centralized:

• Single point of failure
• Requires trust in directory operator
• Vulnerable to censorship
• Scalability bottlenecks

Percolated discovery advantages:

• No single point of failure
• Zero-trust architecture
• Censorship-resistant
• Horizontal scalability

Distributed Hash Tables (DHTs)

DHT-based systems (Kademlia, Chord, etc.) provide decentralized lookup:

DHT characteristics:

• Deterministic routing
• Logarithmic lookup complexity
• Requires network participation

Percolated discovery differences:

• Non-deterministic (follows least resistance)
• Variable lookup complexity (depends on percolation state)
• Optional participation (can use without contributing)
• End-verifiable (DHTs typically trust routing)

Blockchain-Based Discovery

Some systems use blockchains for discovery:

Blockchain characteristics:

• Global consensus on state
• High availability
• Expensive writes

Percolated discovery differences:

• No global consensus required
• Eventual consistency
• Lightweight (no mining/staking)
• Privacy-preserving options

Web-of-Trust Models

PGP-style web-of-trust for key discovery:

Web-of-trust characteristics:

• Social trust relationships
• Manual key signing
• Transitive trust

Percolated discovery similarities:

• Decentralized
• Transitive sharing
• User-permissioned options

Percolated discovery differences:

• Cryptographic verification (not social trust)
• Automated discovery
• Zero-trust percolation

Security Properties

Threat Model

Percolated discovery is designed to resist:

1. Malicious OOBI sources: Cannot forge verifiable information
2. Compromised percolation nodes: Cannot tamper with end-verifiable data
3. Network attackers: Cannot inject false information
4. Censorship attempts: Alternative percolation paths emerge
5. Sybil attacks: End-verifiability prevents identity forgery

Security Guarantees

Authenticity: All discovered information is cryptographically verifiable to its source AID

Integrity: Any tampering with discovered information is detectable through SAID and signature verification

Non-repudiation: Controllers cannot deny information they have signed

Duplicity detection: Conflicting versions of KELs are detectable through ambient duplicity detection

Privacy Considerations

Public discovery: OOBIs can be published openly for maximum availability

Private discovery: OOBIs can be shared only with authorized parties for privacy

Correlation resistance: Private ACDCs use UUIDs to prevent correlation

Selective disclosure: Discovery information can be graduated to reveal only necessary details

Implementation Considerations

Performance Optimization

1. Caching strategies: Cache verified discovery information with appropriate TTLs
2. Parallel discovery: Query multiple percolation sources simultaneously
3. Proximity-based selection: Prefer geographically/network-proximate sources
4. Watcher integration: Use watchers as high-availability discovery hubs

Scalability Factors

• Horizontal scaling: More percolation nodes improve availability
• Non-interactive authorization: Reduces load on original sources
• Eventual consistency: Allows for distributed, asynchronous operation
• Lightweight protocol: Minimal computational and bandwidth requirements

Interoperability

Percolated discovery integrates with:

• HTTP/HTTPS: Standard web protocols for OOBI resolution
• DNS: For URL resolution (discovery only, not authentication)
• QR codes: For compact OOBI encoding
• NFC/Bluetooth: For proximity-based OOBI exchange
• Email/messaging: For OOBI distribution

Conclusion

Percolated discovery represents a fundamental innovation in decentralized information discovery, combining mathematical rigor (Invasion Percolation Theory) with practical cryptographic security (end-verifiability) to create a scalable, zero-trust discovery mechanism. By transforming discovery from a security problem into an availability problem, it enables truly decentralized identity infrastructure without centralized directories or trusted intermediaries.

The mechanism's integration with KERI, ACDC, and OOBI protocols creates a comprehensive ecosystem for verifiable digital identity and credentials, where discovery naturally optimizes for efficiency while maintaining strong security guarantees through cryptographic verification rather than trusted infrastructure.