Introduction to rho calculus

Hey, devs and future devs! This post is to help everyone get a basic understanding of Reflective Higher-Order Calculus (rho-calc), and understand why RChain uses this calculus model to build and solve blockchain scalability and security.

Computational mathematics in blockchain technology

Blockchain platforms such as Bitcoin and Ethereum helped pave the way for enabling smart contracts to run on distributed networks. Most current blockchains are based on a sequential model of computation, just like most commonly used programming languages. With all of their contributions, they lack the efficiency needed to build fast, scalable applications at industry scale utility (the likes of Visa and Facebook). A lot of platforms see the need to scale, but how they plan to accomplish this is different.
Current blockchains can’t handle heavy user load without slowing down significantly. We’ve seen examples of this “network-clog” many times in the past few years, from ICOs to CryptoKitties to Coinbase not batching Bitcoin transactions.
That’s a major limitation of the current blockchain technologies. The languages are based on models of computation that lack concurrency. In the concurrent programming paradigm, multiple computations can be executed during overlapping time periods, independently instead of sequentially. Imagine a smart contract (or system) smart enough to say “Hmm. John is buying coffee, and it’s unrelated to Jane buying a bagel across the street because they are buying two different things.” So, instead of Jane having to wait for John’s coffee transaction to be verified on the blockchain before she can buy her bagel, the two processes can execute independently and efficiently, while still using the same shared database.

Rho calculus | Designed for scaling distributed networks

Rho calculus is derived from ????-calculus (pi calculus). ????-calculus was one of the first computational calculi that seeks to model concurrent processes utilizing mobility, names, and interaction on different channels. Channels can pass messages back and forth and synchronize if necessary.
What does all this mean? Mobility is the ability to interpret a dynamically changing network topology. A name can be understood as giving a channel a unique identity, which can then be used to locate and modify data. A channel is a communication link between two processes. Computation is the message passing between channels, and because channel names can be passed along channels, ????-calculus can model concurrent processes on dynamically changing networks.

The reasoning for rho calculus

Greg Meredith started with pi calculus because it was the only calculus that had four traits he considered necessary for building a blockchain: completeness, compositionality, concurrency, and complexity (ability to measure resource use). Now, having a model with those four properties, Greg decided to add some flavor into the mix that would make it truly safe and scalable. That flavor is Reflection, and that’s why he named this new calculus Reflective Higher-Order Calculus (rho calculus).   
Reflection allows a program to inspect or operate on itself by modifying its data to create a newer version of itself. This feature of reflection is what makes metaprogramming possible. The reflective behavior in rho-calc allows the programming language to convert syntax into modifiable data, and convert that modified data back into a new program. As Greg is fond of saying, “People don’t write programs. Programs write programs.”
Higher-order calculus enhances mobility by allowing not only names to be passed as values on communication channels, but also processes. “One result of being able to investigate the internal structure of a name is that processes may be serialized to a channel and then deserialized upon being received, which means that processes may not only communicate signals to one another, they may communicate full-form processes to one another.
In a video interview called The Scalable, Concurrent and Performant Blockchain, Greg and Nash Foster talked about how namespaces have a structure that makes it easy to find and separate data, with a nearly infinite number of possible addresses, namespaces is defined as a set of named channels.  This feature, combined with processes interacting by message-passing, allows for not just concurrency but sharding into different address spaces. Greg said: “When you start to notice how those features interact (compositionality, concurrency, completeness, etc.), you will see that the model of computation is auto sharded. So, it’s not just giving you concurrency. It gives you concurrency with this notion of sharding built in.”

Where to go from here?

Hopefully this clears up some of the questions you may have, and gives you a brief history lesson on how RChain came to be. If you want a more in depth look into the calculus itself, feel free to read the resource article by Greg Meredith, Reflective Higher-Order Calculus It goes more into the history and gives a breakdown on how the algorithms work as well as the difference between First order and Higher-order. If you want to dive right into the language, check out the Rholang tutorial. Happy Coding!
If you are interested in the more theoretical design of computational calculi, catch up with the recordings of Greg Meredith’s course on the RChain YouTube channel.
Note*** On September 3rd through the 6th, RChain will be launching its testnet version of the Mercury mainnet release (expected in Q4 2018) in Berlin for the RCon3 conference. If you like learning about rho calculus and dApps that can run on RChain’s platform, then register or get more information on the RCon3 site. If you want to participate in the testnet, join the node testing group.

  1. Parrow, J. (n.d.). An Introduction to the pi-calculus. Retrieved June 19, 2018
  2. Simon Marlow.(Simon Marlow at USI) Parallel and concurrent programming in Haskell – Simon Marlow at USI [Video File]
  3. Cartwright, C. (2000, January 07). What is Concurrent Programming? Retrieved June 22, 2018
  4. Milner, R. (2006, May 05). The Polyadic pi-Calculus: A Tutorial. Retrieved June 17, 2018
  5. L. G. Meredith(05-16-2005) A Reflective Higher-Order Calculus. Retrieved on June 18, 2018
  6. L. G. Meredith and Matthias Radestock (n.d) Namespace logic: A logic for a reflective higher-order calculus. Retrieved on June 19, 2018
  7. L.G Meredith and Michael Stay(2017, July 09) Higher Category models of the Pi-Calculus. Retrieved June 19, 2018.  
  8. Davide Sangiorgi (n.d) From Pi-Calculus to Higher-Order Calculus – and Back. Retrieved on June 18, 2018
  9. Davide Sangiorgi (n.d) Expressing Mobility in Process Algebras: First-Order and Higher-Order Paradigms. Retrieved on June 18, 2018
  10. Zwass, V. (2017, August 17). Agent. Retrieved June 17, 2018
  11. Dimitrios Kouzapas, Jorge A. Pérez , and Nobuko Yoshida (n.d) Characteristic Bisimulations for Higher-Order Session Processes. Retrieved June 20. 2018
  12. Groote, J. (n.d.). Strong bisimulation – Basic behavioural equivalences. Retrieved June 17, 2018
  13. Davide Sangiorgi (n.d) Bisimulation for Higher-Order Calculi*. Retrieved June 20,2018
  14. Davide Sangiorgi (n.d) The Orgins of Bisimulation and Coinduction. Retrieved June 21,2018   
  15. Jeannette M. Wing (2002, December 27)  FAQ on Pi-Calculus Retrieved June 21, 2018
  16. Landin, P. J. (1965). A Correspondence between ALGOL 60 and Church’s Lambda-notation.
  17. Matej kosik (12, November 2005) Lambda Calculus Retrieved July 1, 2018
  18. https://www.reddit.com/r/ethereum/comments/6ihw6p/can_someone_please_explain_nonce_to_me/