Rippled Audit

Path Selection & Rippling

Unless it involves direct XRP-to-XRP transfers, a payment sent accross the network may entail exchanging various currencies for others and/or the transfer of a currency issued by a single gateway from one party to another, a process known as rippling. In the case of a cross-border transactions, it is often the case the sender has access to funds in one currency while the recipient only accepts another. Each account on the network has extended trust to an issuer of their local currency, and the network needs to bridge the gap.

By leveraging the Payments and Order Book features, rippled is able to facilitate the movement of funds by path selection by incorporating open orders to convert payments between currencies on the route between source and destination.

As we saw in Payments the path::RippleCalc class is primarily responsible for implementing the path execution and rippling logic.

src/ripple/app/tx/impl/Payment.cpp - calculating paths

396
397
398
399
400
401
402
403
404
   rc = path::RippleCalc::rippleCalculate (
       pv,
       maxSourceAmount,
       saDstAmount,
       uDstAccountID,
       account_,
       spsPaths,
       ctx_.app.logs(),
       &rcInput);

rippleCalculate currently implements the path calculation & rippling logic through one of two logic paths, depending on whether the Flow Amendment is in effect (which it currently is as of rippled v0.33.0 / 2016-10-21). The common Flow logic is invoked from the Order fullfillment subsystem as well (provided the FlowCross Ammendment is in effect).

src/ripple/app/tx/impl/CreateOffer.cpp - calculating paths via flow

739
740
741
742
743
744
745
746
747
   // Call the payment engine's flow() to do the actual work.
   auto const result = flow (psb, deliver, account_, account_,
       paths,
       true,                       // default path
       ! (txFlags & tfFillOrKill), // partial payment
       true,                       // owner pays transfer fee
       true,                       // offer crossing
       threshold,
       sendMax, j_);

Path Init

Before starting, a PaymentSandbox view (pv) is created, passed to rippleCalculate / flow, and finally applied to the active ledger via a call to pv.apply(ctx_.rawView());.

We will discuss the classic path selection logic and the newer flow subsystem seperately below.

Classic Path Selection

Should the Flow Ammendment not be in effect, execution will take place through the original logic branch, incorporating the following classes in for branch analysis

  • PathState defining a potential end-to-end path through which value and funds can be transferred, with live state information calculated through active ledger analysis
  • Node - a single 'step' in a path, associated with an account (potentially a funds issuer) or an order books/offer.

The classical path selection logic is implemented in the following manner:

  • The static top level rippleCalculate method instantiates a local rippleCalc instance, forwarding the necessary parameters, and calling the non-static rippleCalculate method on that

    src/ripple/app/paths/RippleCalc.cpp - rippleCalc::rippleCalculate

    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    
           RippleCalc::Output RippleCalc::rippleCalculate (
               PaymentSandbox& view,
    
               // Compute paths using this ledger entry set.  Up to caller to actually
               // apply to ledger.
    
               // Issuer:
               //      XRP: xrpAccount()
               //  non-XRP: uSrcAccountID (for any issuer) or another account with
               //           trust node.
               STAmount const& saMaxAmountReq,             // --> -1 = no limit.
    
               // Issuer:
               //      XRP: xrpAccount()
               //  non-XRP: uDstAccountID (for any issuer) or another account with
               //           trust node.
               STAmount const& saDstAmountReq,
    
               AccountID const& uDstAccountID,
               AccountID const& uSrcAccountID,
    
               // A set of paths that are included in the transaction that we'll
               // explore for liquidity.
               STPathSet const& spsPaths,
               Logs& l,
               Input const* const pInputs)
           {
    
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    
               if (callFlowV1)
               {
                   auto const timeIt = flowV1FlowDebugInfo.timeBlock ("main");
                   RippleCalc rc (
                       flowV1SB,
                       saMaxAmountReq,
                       saDstAmountReq,
                       uDstAccountID,
                       uSrcAccountID,
                       spsPaths,
                       l);
                   if (pInputs != nullptr)
                   {
                       rc.inputFlags = *pInputs;
                   }
    
                   auto result = rc.rippleCalculate (compareFlowV1V2 ? &flowV1FlowDebugInfo : nullptr);
    
  • From there we check if the default path should be added or if the user specified paths.

    src/ripple/app/paths/RippleCalc.cpp - rippleCalc#rippleCalculate

    276
    277
    
           TER RippleCalc::rippleCalculate (detail::FlowDebugInfo* flowDebugInfo)
           {
    
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    302
    
             if (inputFlags.defaultPathsAllowed)
             {
                 if (!addPathState (STPath(), resultCode))
                     return resultCode;
             }
             else if (spsPaths_.empty ())
             {
                 JLOG (j_.debug())
                     << "rippleCalc: Invalid transaction:"
                     << "No paths and direct ripple not allowed.";
    
                 return temRIPPLE_EMPTY;
             }
    
  • We iterate over the specified paths, and create local nodes, more on addPathState below.

    312
    313
    314
    315
    316
    
             for (auto const& spPath: spsPaths_)
             {
                 if (!addPathState (spPath, resultCode))
                     return resultCode;
             }
    
  • We select the best path from the list and compute total liquidity (more on PathCursor and PathState::lessPriority below)

    347
    348
    349
    350
    351
    
             for (auto pathState : pathStateList_)
             {
                 if (pathState->quality())
                     // Only do active paths.
                 {
    
    363
    364
    
                     PathCursor pc(*this, *pathState, multiQuality, j_);
                     pc.nextIncrement ();
    
    378
    379
    380
    381
    382
    383
    
                     if (!pathState->quality())
                     {
                         // Path was dry.
    
                         ++iDry;
                     }
    
    417
    418
    419
    420
    421
    422
    423
    424
    425
    426
    
                     if ((!inputFlags.limitQuality ||
                          pathState->quality() <= uQualityLimit)
                         // Quality is not limited or increment has allowed
                         // quality.
                         && (iBest < 0
                             // Best is not yet set.
                             || PathState::lessPriority (
                                 *pathStateList_[iBest], *pathState)))
                         // Current is better than set.
                     {
    
    436
    
                         iBest = pathState->index ();
    
  • Finally we apply it and cleanup

    463
    464
    465
    466
    
              if (iBest >= 0)
              {
                  // Apply best path.
                  auto pathState = pathStateList_[iBest];
    
    487
    488
    
                  // Apply best pass' view
                  pathState->view().apply(view);
    
    577
    578
    579
    580
    581
    582
    583
    584
    585
    586
    587
    588
    
             if (resultCode == tesSUCCESS)
             {
                 auto viewJ = logs_.journal ("View");
                 resultCode = deleteOffers(view, unfundedOffersFromBestPaths, viewJ);
                 if (resultCode == tesSUCCESS)
                     resultCode = deleteOffers(view, permanentlyUnfundedOffers_, viewJ);
             }
    
             // If isOpenLedger, then ledger is not final, can vote no.
             if (resultCode == telFAILED_PROCESSING && !inputFlags.isLedgerOpen)
                 return tecFAILED_PROCESSING;
             return resultCode;
    

src/ripple/app/paths/PathState.cpp - PathState::lessPriority

We can see the ultimate criteria through which paths are compared implemented in PathState::lessPriority which returns true/false indicating if the first path is of less priority than the second (in other words true if the second path is the better one)

79
80
81
82
83
84
85
86
87
88
89
90
91
   bool PathState::lessPriority (PathState const& lhs, PathState const& rhs)
   {
       // First rank is quality.
       if (lhs.uQuality != rhs.uQuality)
           return lhs.uQuality > rhs.uQuality;     // Bigger is worse.

       // Second rank is best quantity.
       if (lhs.saOutPass != rhs.saOutPass)
           return lhs.saOutPass < rhs.saOutPass;   // Smaller is worse.

       // Third rank is path index.
       return lhs.mIndex > rhs.mIndex;             // Bigger is worse.
   }

Classic Path Selection Structure and Quality

Continuing to dive into the logic from above, we find the path expansion detailed in the official documentation implemenented via rippleCalc#addPathState, which instaniates a new PathState instance and dispatches to PathState#expandPath and PathState#pushNode as detailed below:

With the implementation of the flowchart above we see the selected paths / nodes are setup in a manner for subsequent expansion and live evaluation. It should be noted that at a high level, the Flow logic works in a similar way, constructing abstract Strand instances to evaluate payment paths, but differs in it's implementation and constraints (more on this below).

The final piece is the calculation of the liquidity / quality factor, through which paths are evaluated to ensure user specified constraints are met (sendMax, deliverMin, etc) and to calculate the total level of liquidity transferred.

The functionality is implemented via the PathCursor class, which is constructed during path evaluation and comparison as we saw earlier, and whose nextIncrement method is invoked to compute the path's total transfer of liquidity:

And with that we see the complete classic path implementation, through which user specified paths are converted into PathState and Node instances in rippled which is then evaulated against the current ledger to transfer issuances accross the network.

Flow based Path Selection

Recent versions of rippled incorporate alternative path computation logic implemented in the Flow subsystem, which is currently being used to facilitate cross-currency/issuer Payments. While the logic to use Flow to satisfy newly created Offers is in place, that branch will not be activated until the FlowCross amendment is ratified.

We can see the top level flow function signature:

36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
   /**
     Make a payment from the src account to the dst account
     @param view Trust lines and balances
     @param deliver Amount to deliver to the dst account
     @param src Account providing input funds for the payment
     @param dst Account receiving the payment
     @param paths Set of paths to explore for liquidity
     @param defaultPaths Include defaultPaths in the path set
     @param partialPayment If the payment cannot deliver the entire
              requested amount, deliver as much as possible, given the constraints
     @param ownerPaysTransferFee If true then owner, not sender, pays fee
     @param offerCrossing If true then flow is executing offer crossing, not payments
     @param limitQuality Do not use liquidity below this quality threshold
     @param sendMax Do not spend more than this amount
     @param j Journal to write journal messages to
     @param flowDebugInfo If non-null a pointer to FlowDebugInfo for debugging
     @return Actual amount in and out, and the result code
   */
   path::RippleCalc::Output
   flow (PaymentSandbox& view,
       STAmount const& deliver,
       AccountID const& src,
       AccountID const& dst,
       STPathSet const& paths,
       bool defaultPaths,
       bool partialPayment,
       bool ownerPaysTransferFee,
       bool offerCrossing,
       boost::optional<Quality> const& limitQuality,
       boost::optional<STAmount> const& sendMax,
       beast::Journal j,
       path::detail::FlowDebugInfo* flowDebugInfo=nullptr);

This top level flow method itself doesn't do much work outside dispatching to toStrands so as to retrieve the list of Strand instances which are simply Vectors of of Steps used to implement each stage of a ripple path. Once instantiated the strands are passed to the template-version of the flow method to complete execution depending on the nature of the assets being transfferred

55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
   path::RippleCalc::Output
   flow (
       PaymentSandbox& sb,
       STAmount const& deliver,
       AccountID const& src,
       AccountID const& dst,
       STPathSet const& paths,
       bool defaultPaths,
       bool partialPayment,
       bool ownerPaysTransferFee,
       bool offerCrossing,
       boost::optional<Quality> const& limitQuality,
       boost::optional<STAmount> const& sendMax,
       beast::Journal j,
       path::detail::FlowDebugInfo* flowDebugInfo)
   {
87
88
89
90
       // convert the paths to a collection of strands. Each strand is the collection
       // of account->account steps and book steps that may be used in this payment.
       auto sr = toStrands (sb, src, dst, dstIssue, limitQuality, sendMaxIssue,
           paths, defaultPaths, ownerPaysTransferFee, offerCrossing, j);
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
       // The src account may send either xrp or iou. The dst account may receive
       // either xrp or iou. Since XRP and IOU amounts are represented by different
       // types, use templates to tell `flow` about the amount types.
       if (srcIsXRP && dstIsXRP)
       {
           return finishFlow (sb, srcIssue, dstIssue,
               flow<XRPAmount, XRPAmount> (
                   sb, strands, asDeliver.xrp, partialPayment, offerCrossing,
                   limitQuality, sendMax, j, flowDebugInfo));
       }

       if (srcIsXRP && !dstIsXRP)
       {
           return finishFlow (sb, srcIssue, dstIssue,
               flow<XRPAmount, IOUAmount> (
                   sb, strands, asDeliver.iou, partialPayment, offerCrossing,
                   limitQuality, sendMax, j, flowDebugInfo));
       }

       if (!srcIsXRP && dstIsXRP)
       {
           return finishFlow (sb, srcIssue, dstIssue,
               flow<IOUAmount, XRPAmount> (
                   sb, strands, asDeliver.xrp, partialPayment, offerCrossing,
                   limitQuality, sendMax, j, flowDebugInfo));
       }

       assert (!srcIsXRP && !dstIsXRP);
       return finishFlow (sb, srcIssue, dstIssue,
           flow<IOUAmount, IOUAmount> (
               sb, strands, asDeliver.iou, partialPayment, offerCrossing,
               limitQuality, sendMax, j, flowDebugInfo));

toStrands creates the default path if necessary, and the iterates over each user-specified path invoking toStrand to instantiate the actual objects. toStrand simply dispatches to toStrandV1 or toStrandV2 depending on if the Fix 1373 Ammendement is in effect (which as of the writing of this, it currently is).

src/ripple/app/paths/impl/PaySteps.cpp - toStrands

713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
   std::pair<TER, std::vector<Strand>>
   toStrands (
       ReadView const& view,
       AccountID const& src,
       AccountID const& dst,
       Issue const& deliver,
       boost::optional<Quality> const& limitQuality,
       boost::optional<Issue> const& sendMax,
       STPathSet const& paths,
       bool addDefaultPath,
       bool ownerPaysTransferFee,
       bool offerCrossing,
       beast::Journal j)
   {
       std::vector<Strand> result;
739
740
741
742
       if (addDefaultPath)
       {
            auto sp = toStrand (view, src, dst, deliver, limitQuality,
                sendMax, STPath(), ownerPaysTransferFee, offerCrossing, j);
763
764
765
766
767
768
769
       }
       else if (paths.empty ())
       {
           JLOG (j.debug())
               << "Flow: Invalid transaction: No paths and direct ripple not allowed.";
           return {temRIPPLE_EMPTY, std::vector<Strand>{}};
       }
770
771
772
773
774
       TER lastFailTer = tesSUCCESS;
        for (auto const& p : paths)
        {
            auto sp = toStrand (view, src, dst, deliver,
                limitQuality, sendMax, p, ownerPaysTransferFee, offerCrossing, j);
797
798
799
800
801
802
803
        }

        if (result.empty ())
            return {lastFailTer, std::move (result)};

        return {tesSUCCESS, std::move (result)};
    }

src/ripple/app/paths/impl/PaySteps.cpp - toStrand

692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
   std::pair<TER, Strand>
   toStrand (
       ReadView const& view,
       AccountID const& src,
       AccountID const& dst,
       Issue const& deliver,
       boost::optional<Quality> const& limitQuality,
       boost::optional<Issue> const& sendMaxIssue,
       STPath const& path,
       bool ownerPaysTransferFee,
       bool offerCrossing,
       beast::Journal j)
   {
       if (view.rules().enabled(fix1373))
           return toStrandV2(view, src, dst, deliver, limitQuality,
               sendMaxIssue, path, ownerPaysTransferFee, offerCrossing, j);
       else
           return toStrandV1(view, src, dst, deliver, limitQuality,
               sendMaxIssue, path, ownerPaysTransferFee, offerCrossing, j);
   }

toStrandV1 and toStrandV2 are implemented above and faciliate the expansion of the pathspec into the Vector of Steps, each item a concrete subclass of StepImp implementing the context-specific Step implementation logic.

Finally we can see in the templatized flow method, Strand Steps are iterated over with the rev and fwd methods implemeneted in the concrete step instances being called to actually perform the path analysis and execution:

src/ripple/app/paths/impl/StrandFlow.h - StrandResult flow<class TINAmount, classTOutAmount>

79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
   /**
       Request `out` amount from a strand
       @param baseView Trust lines and balances
       @param strand Steps of Accounts to ripple through and offer books to use
       @param maxIn Max amount of input allowed
       @param out Amount of output requested from the strand
       @param j Journal to write log messages to
       @return Actual amount in and out from the strand, errors, offers to remove,
               and payment sandbox
     */
    template<class TInAmt, class TOutAmt>
    StrandResult <TInAmt, TOutAmt>
    flow (
        PaymentSandbox const& baseView,
        Strand const& strand,
        boost::optional<TInAmt> const& maxIn,
        TOutAmt const& out,
        beast::Journal j)
    {
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
            for (auto i = s; i--;)
            {
                auto r = strand[i]->rev (*sb, *afView, ofrsToRm, stepOut);
                if (strand[i]->isZero (r.second))
                {
                    JLOG (j.trace()) << "Strand found dry in rev";
                    return {tecPATH_DRY, std::move (ofrsToRm)};
                }

                if (i == 0 && maxIn && *maxIn < get<TInAmt> (r.first))
                {
                    // limiting - exceeded maxIn
                    // Throw out previous results
                    sb.emplace (&baseView);
                    limitingStep = i;

                    // re-execute the limiting step
                    r = strand[i]->fwd (
                        *sb, *afView, ofrsToRm, EitherAmount (*maxIn));
                    limitStepOut = r.second;
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
           bool const inactive = std::any_of(
            strand.begin(),
            strand.end(),
            [](std::unique_ptr<Step> const& step) { return step->inactive(); });

        return Result(
            get<TInAmt>(strandIn),
            get<TOutAmt>(strandOut),
            std::move(*sb),
            std::move(ofrsToRm),
            inactive);
      }
      catch (FlowException const& e)
      {
          return {e.ter, std::move (ofrsToRm)};
      }
    }

Actual implementation of each step is left up to the reader to investigate (though perhaps we will elaborate in future revisions of this analysis), but can be seen by inspecting the actual StepImp subclasses: