Have you ever been in your favorite city, needing to call a taxi and having first to install an application on your smartphone in addition to the 10 previously installed taxi apps? What if you could use a single application wherever you go to book your rides regardless of whether it is a taxi, public transport ride, or e-scooter?
In this post, we explain how we can use Daml and a distributed ledger such as Canton (canton.io) to write such an app that is beneficial for both the service providers (transport operators), the travelers, and the drivers. We will first discuss the design and implementation in Daml and then see that without changes to the code, we can deploy the application to run on a decentralized ledger in a scalable, resilient, and open way.
An Informal Description of the Problem
In order to give a brief overview of the problem, let’s consider the situation from the perspective of a traveler—let’s call her Alice—who wants a ride from the main train station to her office. When specifying her ride request, Alice gives her pickup location (the train station), drop off location (the office), and the maximum time she agrees to wait before being picked up. She wants the pickup to happen as soon as possible and to spend as little time as possible inside the vehicle.
A simplified, positive path is as follows:
- Alice sends a ride request to the operator (transportation provider)
- The transport provider collects the state of the vehicles (current location and planned actions) and makes a ride proposal (with a specific vehicle assigned)
- Alice accepts the ride proposal
- A new mission (with Alice’s pickup and drop off locations) is sent to the vehicle
The above flow can fail if no vehicle can reach Alice’s pickup location early enough (within her specified maximum waiting time) or if she rejects the ride proposal.
We may think from the above figure that the operator is the central entity governing the ride-booking process. However, we will see below that the operator is one party among others, together with the vehicles, the traveler, and the bank, and that multiple operators can be involved.
Benefits of a Decentralized Application
We present here some of the benefits of implementing a decentralized application deployed with a synchronization protocol we call Canton. We also bring in some features that come for free thanks to the Daml language. More details about the topology can be found in the Distributed setting section below.
On the operational side, vehicles can seamlessly connect to different nodes running the application, which allows to balance the load (e.g., routing computations) and increase scalability. Moreover, the ability to connect a vehicle to different nodes also improves the resiliency of the system.
On the traveler side, it is possible to connect to several providers, thus getting a unified view containing offers from the different providers. This behavior is similar to what an aggregator would provide.
For the drivers, the ability to connect to different nodes means they can belong to different fleets at the same time, and are thus able to propose rides to different operators, unlike in most current systems.
The atomicity of our protocol also enables transactions that span multiple vehicles: booking two legs of a journey (e.g., round trip), removing a ride from one vehicle and assigning it to another, and so on. The ability to handle such transactional atomicly is very important (e.g., to avoid the situation where only part of a round trip is confirmed or canceled) and is notoriously difficult in a distributed system. Such flows are enabled without the need for the programmer to actually focus on these aspects.
Finally, it is worth mentioning that the authentication of the different actors (including the drivers/vehicles) is handled easily with Daml. In addition, the privacy of the different views (vehicles plans, traveler rides, bank transactions, etc.) results directly from specific features of our language. We’ll discuss these in the next section.
Daml Modeling
In this section, we describe the implementation of the application in Daml. We first present the different actors and the parties involved and discuss how the state is modeled. In the next post, we will demonstrate the different steps in the booking flow. Finally, we briefly explain what additional pieces are required in order to simulate such a system on a local machine.
Actors, parties, and state
Looking back at the figure depicting the simple flow above, we see that the following actors are involved: a traveler (Alice), a few vehicles, and an operator (or transportation provider). Let’s consider the different actors separately.
Travelers
Each traveler is modeled as a Daml party and can request rides.
Vehicles and Their Properties
For a given vehicle, we separate its state into two parts: an immutable one and a mutable one. The immutable one contains properties that do not change over time and can include seating capacity, maximal speed, and certain other characteristics (fuel vs. electric, energy profile, license plate, etc). For the sake of simplicity, we consider in this example only the speed, and we can thus write the vehicle properties as the following template:
template VehicleProperties
with
operator: Party -- A vehicle is associated to an operator
id: VehicleId -- Vehicle identifier
speed: Decimal
where
signatory operator
observer id.driver -- Driver should be able to see the properties
-- For a given operator, name of the vehicle should be unique
key (operator, id.name): (Party, Text)
maintainer key._1
data VehicleId = VehicleId
with
driver: Party
name: Text
As we can see, in addition to the actual vehicle properties (here, the speed), we also associate the operator and a vehicle identifier, which contains both information about the driver as well as a name for the vehicle. In terms of authority and privacy, the operator is the sole signatory on the contract and the driver is added as an observer.
On the other hand, the mutable part consists of the last known location of the vehicle (space and time) as well as information about activities it has to perform (pickup and dropoff of travelers):
template Vehicle
with
operator: Party
id: VehicleId
lastTsLocation: TsLocation
plan: [RideActionCid] -- List of activities to perform (pickups and drop offs)
where
signatory operator
observer id.driver
key (operator, id.name): (Party, Text)
maintainer key._1
data TsLocation = TsLocation with time: Time, space: Location
data Location = Location with x: Decimal, y: Decimal
The list of stakeholders of this template is exactly the same as for the vehicle properties one.
The separation between properties and state (immutable and mutable) provides the ability to keep contract instances as small as possible, which is useful, since the vehicle contract is frequently “updated” (each time a ride is added or removed from the vehicle). For a similar reason, some updates of the vehicle state (last known location, dropping finished activities) is done only when needed, and not eagerly.
Unsurprisingly, the last piece is the fleet, which contains the list of all vehicles managed by the operator:
template Fleet
with
operator: Party
vehicles: [VehicleId]
where
signatory operator
key operator: Party
maintainer key
Again, we notice that the fleet is mostly immutable: it needs to be updated only when a vehicle is added or removed to the fleet, not when the state of a vehicle changes.
Drivers
Each driver is represented by a party and associated with a vehicle. Note that we could also directly represent vehicles by parties. This would also make sense, especially if the fleet consists of autonomous vehicles.
Bank
In addition to the parties described before, we also consider a bank with which travelers hold bank accounts. These accounts can be used to wire money and pay for the ride. In the description of the flows below, we will mostly ignore this part. In practice, we would instead integrate with a payment gateway.
In the next post, we’ll look at the booking flow and how Canton enables the deployment and allows for the connection and synchronization of different ledger instances while still maintaining privacy and integrity.
Connect to our daml developers community and shape the future of Blockchain software.
Booking a Ride With a Smart Contract App
The life of a booking starts with a TravelerAccount created for Alice by the operator. On this contract, Alice can exercise the choice RequestRide that creates a RideRequest. The RideRequest is then handled by the operator, who can either reject it (in case there is no vehicle available to serve the ride request) or create a RideProposal, which contains a proposed pickup time, a dropoff time, and a fare.
Alice then can either accept or reject the ride proposal. If she chooses to accept, an instance of a RideProposalAccepted is created. Finally, the operator triggers the creation of the Ride, *Pickup,*and Dropoff contracts, and the plan of a vehicle is updated.
The flow can be visualized in the following diagram while the different templates and choices that can be exercised on them are shown in the table below.
At this point, you may wonder why we need the RideProposalAccepted contract and why we cannot directly trigger the final step (ride creation and fleet update) directly on the RideProposal. The reason is that Alice, our traveler, is a controller on the RideProposal instance but is not an observer of the fleet, which means that she is not authorized to see the Fleet and Vehicle contracts and exercise choices on them. By adding one more step in our propose-accept pattern, we make sure that the whole flow is properly authorized.
From a Ride Request to a Ride Proposal
We now discuss in more detail the ride request and its processing by the operator. Implementations of the ride requests and proposals as data structures are rather straightforward:
template RideRequest
with
operator: Party
traveler: Party
origin: Location
destination: Location
maximumWaitingTime: RelTime -- Maximum time before pickup
where
signatory traveler
ensure (origin /= destination)
template RideProposal
with
operator: Party
traveler: Party
vehicleId: VehicleId -- Assigned vehicle
rideRequestCid: ContractId RideRequest
rideRequestTime: Time
pickupTime: Time -- Initial planned pickup time
dropoffTime: Time -- Initial planned drop off time
fare: Decimal -- Price of the ride
where
signatory operator
The biggest part is the processing of the request by the operator. The different steps that we need to perform are the following:
- Gather the list of all vehicles and their properties
- Find the list of vehicles that could serve the ride (in our simplified setting, we only need to check that the vehicle can reach the pickup location in time)
- If the list is empty, reject the ride; otherwise, select the vehicle which is the closest to the new pickup and create a ride proposal
These high-level steps yield the following choice on the RideRequest template.
controller operator can
nonconsuming RideRequest_Process: Either (ContractId RideRequestRejected) (ContractId RideProposal)
do
(_, fleet) <- fetchByKey @Fleet operator
time <- getTime
-- List all the vehicles and their properties
vehiclesAndProperties <- forA fleet.vehicles (\id -> do
(_, vehicle) <- fetchByKey @Vehicle (operator, id.name)
(_, properties) <- fetchByKey @VehicleProperties (operator, id.name)
pure (vehicle, properties))
let cRideRequest = C.RideRequest with ..
{-
Algorithmic helper that returns `Optional RideMatchingData`, where None
indicates that no vehicle can serve the ride and `Some RideMatchinData`
contains information about the vehicle that can serve the ride (including
pickup time, drop off time and the fare).
-}
maybeMatchingCandidate <- findBestMatchingCandidate
vehiclesAndProperties cRideRequest
case maybeMatchingCandidate of
None -> do
archive self
fmap Left
(create RideRequestRejected with reason = "No vehicle available", ..)
Some rideMatchingData -> fmap Right
(create RideProposal with
vehicleId = rideMatchingData.vehicleId
fare = rideMatchingData.fare
pickupTime = rideMatchingData.pickupTime
dropoffTime = rideMatchingData.dropoffTime
rideRequestCid = self
rideRequestTime = time, ..)
On Delays, Concurrency, and Transactions
Several assumptions and simplifications are made in our simple implementation. The first is that every party will exercise his/her choices quickly. If that is not the case, e.g., if Alice waits a few minutes before accepting the ride proposal, then the offer made by the operator may not be feasible anymore. In particular, the pickup and the dropoff time need to be recomputed.
Moreover, concurrency issues can arise when multiple travelers try to book rides in parallel. To see why, consider the following situation:
- Alice emits a ride request and gets a proposal
- Bob emits a ride request and gets a proposal assigned to the same vehicle as Alice
- Alice accepts her proposal
Now, when Bob accepts his ride proposal, the vehicle that is assigned is already heading towards Alice, which means that the offer is no longer valid (or not without significantly increasing the delay before Bob’s pickup). Again, this can be solved by adding additional checks in the final transaction of the flow (choice CreateRideAndAddToFleet of the RideProposal_Acceptedtemplate).
Finally, note that the characteristics of Daml can alleviate some inherent issues of such a system:
- By wrapping most of the side effects in the final transaction, one can ensure that creation of the ride, update of the state of the fleet, and payment for the ride happen atomically
- Using contract ids, it is straightforward to check that the current state of the vehicle corresponds to the state of the vehicle when the ride proposal was made, thus decreasing the risk of concurrent updates
Algorithmic Considerations
In the creation of the ride proposal, we chose a naïve and sub-optimal algorithm. For the purpose of simplicity, we decided to select the vehicle that is the closest to the pickup location, in case there are multiple candidate vehicles. Another possibility would be to choose the vehicle that can drive Alice from her pickup location to her destination as quickly as possible, or a combination of these two criteria.
In general, if you allow ridesharing (i.e., multiple travelers sharing the vehicle during a portion of their journeys), pre-booking (booking in advance), or specifying the desired arrival time instead of the desired departure time, then the selection of the best possibility to serve the ride is a non-trivial task (indeed, the problem is a generalization of the traveling salesman problem).
Additionally, taking routing constraints and traffic into account, as well as tracking the vehicle precisely and in real time, is operationally difficult. We neglect all these issues and focus instead on high-level modeling.
Note that this choice is not a restriction: these more complex algorithms could be designed and implemented in parallel. Moreover, one could also perform some of the computations off-ledger in order to protect the IP of the algorithms. In that case, the ledger would only capture the result of such computations.
The Missing Pieces for a Local Simulation
In order to be able to run a complete workflow locally, two important pieces are missing:
- Routing, to compute drive distance and time between locations (vehicle current locations, pickups, drop offs) and simulate vehicle movement
- Matching, to decide whether a ride can be accepted and which vehicle should serve it
In order to perform real routing computation, one usually relies on an external provider (e.g., Google Maps, local instance of OSRM server, etc). For the sake of simplicity (and since routing is orthogonal to the problem we’re solving), we can model vehicle location as tuples (x, y) that represent points in the Euclidean space. We then assume that vehicles drive between such points in straight lines at constant speed.
Given a vehicle plan (pickups and dropoffs to visit), its last known location and the current time (in our case, the ledger time) it is then possible to infer:
- The activities that are already done and that should be dropped from the plan
- The current location of the vehicle (using interpolation between points when necessary)
Similarly, we can implement a simplistic matching algorithm that only considers appending a new ride at the end of a plan. The best candidate is then the vehicle whose last dropoff (or current location, in case of an empty) is the closest to the new pickup.
Distributed Setting
Now that we have seen the different flows and building blocks for our application, we discuss the network topology that could be used to deploy our app. The ingredient that enables this deployment is Canton, a synchronization protocol that allows for the connection and synchronization of different ledger instances while maintaining privacy and integrity. This allows us to see the inter-connected ledgers as a virtual global ledger (see overview and key concepts).
The topology of Canton is flexible and is independent of the different parties mentioned above. One extreme case would be where all parties would be hosted by a single participant node: this corresponds to a fully centralized system managed by the transportation provider. On the other hand, richer topologies allow us to build a platform that possesses scalability, resiliency, and openness.
As an example, let us discuss the topology depicted by the figure below. On the traveler side, any number of nodes can be deployed and connected to the domain. On the operational side, one transportation entity (consisting of a set of vehicles and their operator) can be either hosted on the same node (e.g., “Operations Node 2”) or on different nodes (e.g., “Operations Node 1” and “Vehicles 1”). Moreover, some vehicles (e.g., “Vehicle 2”) can also be hosted by multiple nodes.
This topology enables the traveler to have a unified view over the offers of multiple operators. Moreover, with small changes in the code, it would be possible for vehicles to offer rides to clients of different operators at the same time. For the traveler, it means that a multi-modal journey can be managed in a single workflow. For the operators, it increases the efficiency of the fleet, because idling vehicles can be assigned to other missions, thus reducing the operational costs.
Want to become a Daml developer? Start your journey here.
Also published here.