Analysis of Kadena’s Public Blockchain Protocol
Introduction
Blockchain systems attempt to ensure security by disincentivizing malicious behavior, making it too expensive for a participant to perform double-spend attacks or long-range attacks compared to engaging with the network honestly. Formal proofs of a system’s liveness, consistency, and persistence under certain networking conditions are the current standard of validating a blockchain’s security.
That said, security becomes increasingly difficult to formally prove with “sharded” or parallelized blockchains — partly because these blockchains feature correlations from cross-shard transactions and more complicated protocol design parameters.
We believe that agent-based simulations (ABS) provide a better tool for modeling the security of a multichain blockchain protocol. ABS is used in a variety of fields where the cost of experimentation is high, but estimating your risk accurately is critical for success in production. You’ll find ABS used in algorithmic trading and exchange design, macroeconomic modeling, and self-driving car design.
Blockchain is a great use case for ABS, as our simulations can test certain critical assumptions surrounding block time, adversarial hash power requirements, and the interconnectedness of a network. Gauntlet offers independent ABS analysis for blockchains prior to launch for improving security and functionality.
This post will highlight findings from our research on Kadena’s public blockchain protocol, a parallelized, “braided” Proof of Work (PoW) blockchain called Chainweb. Gauntlet chose to examine Kadena with ABS because its architecture has explicit correlations between cross-chain transactions. This makes it difficult to use standard probabilistic tools to create a closed-form proof. We collaborated with Kadena to produce a peer-reviewed paper and presented our findings during the Europe Security & Privacy IEEE conference in Stockholm (June 2019). Gauntlet provided independent analysis and testing; Kadena shared a detailed formal description of its public blockchain architecture on which to model our simulations.
Kadena’s Proof of Work Blockchain: Brief Overview
Kadena is a braided, PoW network currently in testnet. Based on Bitcoin’s PoW protocol, it hash-links multiple chains to provide additional security and throughput. Key features of the Kadena public blockchain include:
- Multiple PoW chains each maintain their own account-based ledgers.
- All chains can add blocks simultaneously.
- Peer chains cross-reference each other’s previous Merkle roots in a fixed (Peterson) graph structure (Figure 1 shows examples of a single, two, and ten-chain graph).
- Miners mine the entire network (or “braid”).
- Users transfer a native token freely between chains using SPV at the smart contract level.
For more resources on understanding Kadena’s public blockchain, refer to Kadena’s whitepaper and 101 blog post. For a formal description of the architecture, refer to pg. 4–6 in our paper.
The interdependent nature of the Kadena blockchain makes a formal probabilistic proof extremely difficult, if not fundamentally impossible. It is naïve to reduce multichain security to a Bitcoin-like model, as that does not properly account for cross-chain interactions. The Markovian assumption for rational agents is usually violated, and security (hash power) is split over multiple chains, which appears to lower the cost of 51% attacks. Therefore, we turn to Gauntlet’s agent-based simulations.
Gauntlet Networks: Agent Model
Defining Agents
The key to achieving statistically meaningful results is to define a representative set of agents for a system. An agent is defined by state and action spaces and a policy that determines how they choose an action based on a current state. Agents can measure rewards in a variety of manners, including network performance (e.g. adversaries don’t forward blocks).
Designing agents for permissionless systems requires defining both adversarial and “lazy” behavior. With Kadena, we defined these as:
- Adversarial behavior: Not placing hash power on a certain chain
- Lazy behavior: Executing a nothing-at-stake attack because it provides higher expected returns
Our agents adhere to the Byzantine-Altruistic-Rational (BAR) model (Aiyer, et. al, 2005). These agents deviate from intended behavior if in their self-interest and aim to maximize discounted expected utility.
With Kadena, we were solely interested in agents who only measure rewards on-chain (censorship resistance). In the future, once Kadena has launched its mainnet, we plan to include agents who interact with external markets and historical data. Questions arise such as: can a miner sell a future and affect the security model?
We focused on studying agents who censor chains by not placing hash power on certain chains. This approach is not limited to PoW: Validators in Proof of Stake (PoS) systems can attempt to execute a Denial of Service (DoS) attack by not staking on certain shards. We believe these findings will pave the way for future work on evaluating other consensus mechanisms.
Findings
We analyzed three facets of networking in Chainweb’s multichain system: latency, validation, and censorship.
Latency
We found (in Figure 2) that as we increased Chainweb’s base graph size, we see logarithmic scaling and decreasing variance in time to consensus. For liveness, with 57 shards (Hoffman-Singleton graph, Figure 3), a randomized gossip protocol doesn’t need too many simultaneous peers to achieve sub-second latencies. We also found that by the time we got to 10 simultaneous connections, we were close to saturating the high-bandwidth limit.
We believe that these results are useful for protocol developers to assess design decisions and tune parameters such as gossip protocol peers.
Validation
When assessing how Chainweb might perform under more extreme network graphs, we found that when the miner graph was more connected, there was a sharp uptick in expected height increase around half a standard Bitcoin block time (300s). As we decreased connectivity, there was a more gradual height increase (Figure 4). This is expected behavior, as most miners have the same hash power and would receive the block at the same time.
Censorship
Finally and most notably, we discovered that adversaries in the Kadena network experience much greater volatility than their honest counterparts (Figure 5).
Moreover, honest, profit-maximizing agents beat out the censoring agents until those adversaries were in the majority (~50–60%, Figures 6 & 7). This security profile is largely similar to Bitcoin’s current PoW security.
Takeaways and Future Work
Our findings showed that Kadena’s chains appear difficult to censor as long as there are enough rational, profit-maximizing miners in the system. We also demonstrate that agent-based simulations can help assess different protocol design choices, such as how the choice of base graph affects liveness and block time. In Kadena’s case, under many runs, we have assessed that many Proof of Work transactions can securely scale with a network structure that economically benefits all participants.
We’re working on extending our analysis to Proof of Stake and Proof of Space systems, which involve more complicated parameters (i.e. slashing, market-making activities, auctions). We will incorporate data on external markets to analyze Kadena once it is live in mainnet.
