Patrick O'Grady

@patrickogrady

founder Commonware || previously Ava Labs, Coinbase, Stanford

Prime membership

Joined on Oct 26, 2023

  • Vena is an optimistically responsive consensus protocol in the partially synchronous network model tailored for deployment on public blockchains with large validator sets. Vena employs a form of "optimistic" aggregation committee broadcast that when successful results in all participants, including the leader, sending less than $n$ messages in a given round. In the uncommon case that this broadcast fails (robustness is parameterizable), Vena falls back to a single, all-to-all broadcast that guarantees eventual progress in the presence of $f < n/3$ static byzantine faults. It is left to future work to construct a formal proof of correctness for Vena. Overview Simplex Consensus, as proposed by Benjamin Y. Chan and Rafael Pass, is an optimistically responsive consensus protocol that tolerates $f < n/3$ static byzantine faults in the partially synchronous network model. While Simplex Consensus "matches the best optimistic liveness bounds, while at the same time matching and even improving the best known pessimistic liveness bounds (both in expectation and in the worst-case)," its application to public blockchains with large validator sets has been limited by its usage of multiple all-to-all broadcasts per round. Chan and Pass suggest that deployment of Simplex Consensus in such environments may be achieved by "subsampling the committee of voters" to reduce the number of messages sent and received by any participant, akin to Algorand. To bound the probability of failure on any composed committee ($f >= n_c/3$ where $n_c$ is the size of the committee) to a reasonable level, however, Algorand parameterizes each committee to contain thousands of participants drawn from all "online tokens". For some critical operations, the committees are parameterized to include over $5000$ participants (which bounds the risk of failure to $< 2^{-40}$ if $f < 0.2873n$ where $n$ is the total population of "online tokens"). This parameterization is made practically efficient by allowing operators that control multiple selected tokens to aggregate their participation using a technique referred to as "party aggregation". In a scenario where a large population of operators each own the same number of tokens (where each committee participant in expectation has ~1 selected token), the number of messages sent and received by each participant in each round will still be significant. Vena is an extension of Simplex Consensus tailored for deployment on public blockchains with large validator sets that retains both optimistic responsiveness and the ability to confirm blocks with a single, honest leader. Vena takes a different approach to scaling participation than that suggested by Chan and Pass. Rather than subsampling the committee of voters, Vena employs a form of "optimistic" aggregation committee broadcast that when successful results in all participants, including the leader, sending less than $n$ messages in each round. We refer to Vena's aggregation committee broadcast as "optimistic" because validators always attempt to use it at least once for broadcast per round, even in some cases where they end up voting for the "dummy" block (the fallback vote after a timeout). Vena remains correct in the presence of $f < n/3$ static byzantine faults unlike alternative protocols that operate over a subsample of the total population of participants (review the performance of any configuration when $f_p ~= 1/3$). Aggregation committees, popularized by the ETH2 Altair Fork, are some randomly assigned subset of validators that work together to aggregate their communications with a broader network (often by sending messages to other aggregation committees rather than all other participants) to minimize the communication complexity of the broader population of which they are part. Each aggregation committee typically consists of some set of "aggregators" to which all committee members send their messages to. Likewise, each aggregator also pools messages sent by other committees (specifically the aggregators in those committees) and forwards them to all committee members once they have a sufficient stake weight. As long as there exists one honest aggregator in an aggregation committee, messages generated by honest participants in the committee will be forwarded to other aggregators and messages sent to a committee will be forwarded to its participants.
     Like 1 Bookmark
  • Over the last few days, the first Vryx devnet processed 5 billion micropayments at a sustained rate of 100,000 transactions per second (TPS). This test involved 10,000,000 active accounts (2,500,000 active every 60 seconds and 95,000 active every second) sending transfers to each other. The likelihood that a particular account was active in a transaction was given by a Zipf-Mandelbrot Distribution with a standard parameterization (a=~1, b=~2.7). The devnet was validated by 50 equal-weight instances (32 vCPU, 64 GB RAM, 100 GB io2 SSD) running Snowman Consensus across 5 regions (us-west-2, us-east-1, ap-south-1, ap-northeast-1, eu-west-1). Transactions were issued to 1 of 5 API nodes (1 per region) by a single issuer located in eu-west-1. Transactions Per Second You can view the code that powered this devnet here. You can reproduce these results (or modify any of the configuration like the number of validators) in your own AWS account by running this script. If you don't want to deploy your own devnet but want to watch someone do it, you can check out this video. This code is under active development and is not considered production-ready. If you run into any issues, please post them in the HyperSDK repository! Proving Vryx Viability: Sustaining 100k TPS In January, Ava Labs released Vryx, a fortified decoupled state machine replication construction that provided a path to scale the throughput of each Avalanche HyperSDK blockchain instance to over 100,000 TPS. Providing a path and walking that path, however, are two different things. When translating a specification into running code, any engineer will tell you that unknown unknowns can sink any promising project (unforeseen issues with a design render an approach infeasible).
     Like 2 Bookmark
  • Vryx is an extension of previous research on scaling throughput in the HyperSDK [Agreeing on Execution Inputs, Not Execution Results] and familiarity with that work, and the open questions it presents, provides useful context around the motivation for this work. Overview Over the last few years, multiple teams have produced experimental results showing that decoupling transaction replication, sequencing, and execution can significantly increase blockchain throughput [Flow: Separating Consensus and Compute -- Block Formation and Execution][Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus][Bullshark: DAG BFT Protocols Made Practical][Shoal: Improving DAG-BFT Latency And Robustness][Sui Lutris: A Blockchain Combining Broadcast and Consensus][BBCA-CHAIN: One-Message, Low Latency BFT Consensus on a DAG][Mir-BFT: High-Throughput Robust BFT for Decentralized Networks][Mysticeti: Low-Latency DAG Consensus with Fast Commit Path][Aleph: Efficient Atomic Broadcast in Asynchronous Networks with Byzantine Nodes]. Unlike "traditional" blockchains (like Bitcoin) where syntactically and semantically valid transactions are sequenced, executed, and replicated simultaneously in each block, these decoupled constructions are able to better pipeline State Machine Replication (SMR) by disseminating, ordering, and verifying transactions independently. This newly rediscovered approach of "decoupling" State Machine Replication (DSMR), previously detailed by [Separating agreement from execution for byzantine fault tolerant services] and [BASE: Using Abstraction to Improve Fault Tolerance] in the early 2000s, is not without tradeoffs. As a consequence of performing replication prior to sequencing and execution, it is no longer possible to enforce semantic verification of replicated transactions. Let us refer to the number of Replicated Transactions Per Second (whether or not fee-paying/executable) as rTPS, the number of Fee-Paying Transactions Per Second as fTPS, and the number of Invalid Transactions Per Second as iTPS (rTPS - fTPS). This means that the fTPS of DSMR constructions can be far less than rTPS, causing participants to waste valuable resources replicating and verifying invalid transactions (iTPS = rTPS - fTPS). Adversarial issuers (users) employing a mix of cost-effective tactics on a realistic DSMR model can exploit this tradeoff to reduce fTPS to less than 1% of rTPS. Vryx, a fortified DSMR construction that will be employed by the Avalanche HyperSDK and eventually other Avalanche Virtual Machines, mitigates these adversarial issuance attacks for profit-maximizing builders and ensures that any transactions they replicate must pay fees, restoring fTPS = rTPS. Vryx thus enables the HyperSDK to take full advantage of DSMR pipelining without sacrificing the robustness of traditional SMR, which can enforce full syntactic and semantic verification. Because Vryx only introduces additive constraints to DSMR replication and execution (and does not require any changes to consensus), most of its techniques could be incorporated into previously proposed and adopted DSMR constructions to defend against adversarial users. If you prefer long-form video to text, check out the Vryx Overview on YouTube (Slides).
     Like 7 Bookmark
  • Posted to ACP GitHub Discussions on 10/24/23 Proposed as ACP-13 on 10/31/23 Over the last few months, I've spent a lot of time thinking about what changes could be adopted on the Avalanche Network to make Subnets even more attractive to developers (especially new startups/ecosystems just getting started). I think that the most impactful change to consider right now, as you alluded to, would be overhauling the relationship between Subnets/Subnet Validators and the Primary Network. I typed up some background on this topic for those unfamiliar and shared a three-step rollout plan that IMO would better position Subnets in the increasingly competitve "launch your own blockchain" space (could be cleaned up and turned into an ACP). It is worth noting that I also think native interoperability with the Primary Network is critical to attracting developers to Subnets but didn't feel it was worth elaborating on because that functionality will be provided shortly via the Avalanche Warp Messaging (AWM) integration with the C-Chain and the launch of Teleporter. TL;DR, this will allow Subnets to use $AVAX or $USDC as their native token without a trusted intermediary. Background
     Like  Bookmark
  • Originally published as a final project in December 2018 for CS191W at Stanford University Abstract An alternative to StumbleUpon, Hivenet is an implementation of a decentralized and autonomous URL recommender system that proposes a novel method to assign reputation to untrusted peers in a peer-to-peer network: useful originality. To provide context for Hivenet, this paper provides an overview of recommender systems and outlines how existing centralized recommendation systems require users to sacrifice their privacy, expose themselves to bias injection, and give up the ability to export activity data to other (competing) services. Next, this paper proposes a design paradigm on which to base decentralized recommender systems and describes the implementation of two iterations of Hivenet, which is based on this design paradigm. The latter implementation (code), and the main product of this paper, autonomously determines the reputation of untrusted peers by calculating the usefulness of each respective peer’s originality, assigning a unit of reputation to the first peer that discovered a URL that the user rated highly. Finally, this implementation is subjected to a simulation environment that supports the hypothesis that basing reputation on useful originality protects users from malicious peers under reasonable modeling assumptions. Stumbleupon: “Click a Button, Find Something Cool” Garrett Camp, the creator of Stumbleupon, described the early internet service in a simple phrase: “Click a button, find something cool.” [1] Created in 2001, Stumbleupon solved the problem of traversing an ever growing internet by recommending content that it thought users would enjoy based on the ratings of other users that liked similar content. What originally started as an idea shared between friends at the University of Calgary eventually grew to 40 million users that “stumbled” over 60 billion times and drove half of all social traffic on the web. [2] In 2018, however, Garrett Camp announced that the service would shut down amid the increasing competition from social networks. At its closure, StumbleUpon drove only 0.1% of social traffic on the web (which decreased 50% YoY in its last year of existence). [3] A postmortem of the StumbleUpon company and its declining popularity, however, is not the subject of this paper. Rather, this paper proposes how a StumbleUpon clone could be built without relying on any centralized party to collect content ratings, detect malicious peers, and provide content recommendations.
     Like  Bookmark