Percolated discovery is a zero-trust information discovery mechanism based on Invasion Percolation Theory that enables scalable, non-interactive discovery of KERI/ACDC infrastructure endpoints through cryptographically end-verifiable information sharing, where each discoverer can transitively share discoveries without requiring trust in intermediaries or the percolation mechanism itself.
Related Concepts
No related concepts available
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:
Decentralized endpoint discovery: Enables discovery of witness endpoints, watcher networks, and other KERI infrastructure without centralized directories
Scalable information propagation: After initial bootstrap via , subsequent authorization becomes non-interactive, creating highly scalable discovery
Implementation Notes
Critical Implementation Considerations
Cryptographic Verification Requirements
Implementations MUST perform complete cryptographic verification of all discovered information:
KEL Verification: Validate all signatures, hash chains, and witness receipts in discovered KELs
SAID Verification: Recompute SAIDs to ensure content integrity
Key State Validation: Verify that signatures use keys from the correct key state
Witness Threshold: Ensure sufficient witness receipts meet the TOAD threshold
Never trust discovery paths - the entire security model depends on end-to-end cryptographic verification.
Caching Strategy
Implement intelligent caching to optimize percolation performance:
Cache verified KELs with appropriate TTLs based on rotation frequency
Cache witness endpoints to reduce discovery latency
Implement cache invalidation when detecting key rotations
Use BADA policy to balance freshness vs. availability
Error Handling Patterns
Graceful degradation: When discovery fails, use cached information if available within acceptable freshness bounds
Retry with backoff: Implement exponential backoff for transient network failures
Alternative paths: Maintain multiple OOBI sources and try alternatives on failure
Duplicity response: Have clear policies for handling detected duplicity (flag, escalate, reject)
Zero-trust architecture: Eliminates the need to trust discovery intermediaries or the percolation mechanism itself
Privacy-preserving options: Supports both public and private discovery topologies based on user permissions
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:
Discoverers: Entities seeking to discover information about AIDs or infrastructure endpoints
Sharers: Entities that have already discovered information and share it with subsequent discoverers
Controllers: AID controllers who initially publish OOBIs for their infrastructure
Witnesses: Infrastructure components whose endpoints are being discovered
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:
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:
Share their discovery with other entities seeking the same information
Provide OOBIs pointing to their own endpoints where the verified information is available
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:
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:
No challenge-response required: Discoverers can verify information without interacting with the original source
Cached information is verifiable: Previously discovered information remains cryptographically valid
Offline verification possible: Discovery information can be verified without network connectivity to original sources
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:
Trust the OOBI source?: While the OOBI itself is not trusted cryptographically, discoverers may choose to prioritize OOBIs from known sources
Which percolation path?: When multiple discovery paths exist, discoverers may select based on latency, trust relationships, or other criteria
Share discoveries?: Discoverers decide whether to participate in percolation by sharing their discoveries
Public vs. private discovery?: Controllers decide whether to enable public discovery or restrict to permissioned networks
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.
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:
Initial invasion: Fluid enters at a source site
Neighbor evaluation: Examine all dry neighbors of invaded sites
Minimum resistance selection: Invade the neighbor with lowest resistance
Cluster growth: Add newly invaded site to the connected cluster
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)
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.
Consider correlation risks when sharing discovery information
Integration with KERI Components
Witness integration: Implement witness discovery and KERL retrieval
Watcher integration: Support watcher endpoints as percolation super-nodes
Registry discovery: Extend percolation to discover TEL registries for credential status
Delegation chains: Support recursive discovery through delegation hierarchies
Testing Considerations
Test with malicious OOBIs: Verify rejection of unverifiable information
Test network failures: Ensure graceful degradation and retry logic
Test duplicity scenarios: Verify detection and handling of conflicting KELs
Test percolation propagation: Verify information sharing between nodes
Performance testing: Measure discovery latency under various network conditions
Monitoring and Observability
Implement monitoring for:
Discovery success rates: Track successful vs. failed discoveries
Latency metrics: Measure time from OOBI to verified KEL
Cache hit rates: Monitor caching effectiveness
Percolation paths: Track which sources provide successful discoveries
Duplicity events: Alert on detected duplicity for investigation