Category: tech

i’ve been thinking about saml and oauth a lot lately due to work. i’m putting down some of my thoughts here on how i believe they differ in purpose.

lets say there’s COOL WEB APP with a typical authentication using email and password. these creds get transmitted in a HTTP request and server backend verifies the credentials and grants access to user (hopefully user credentials are stored in an encrypted form…).

but there are many situations in which you may not want to be the one in charge of creds. maybe you’re scared. or maybe you want potential users to log in using their existing account with a different service (say, Google or Facebook) for convenience. or both.

if the user authenticates with a third party service (that you trust), you are basically delegating identity verification to a separate service. this is sort of the point of both SAML and OAuth at a high level, but they’re designed for different problems.

oauth

implementing OAuth in the web app lets users of that app access the service through a trusted third party that does the auth. The user goes through a login flow with the third party and eventually the third party grants a token that your app can use to retrieve user information (such as email) that can be used to grant access to the COOL WEB APP.

as a user, i might access multiple services with different oauth flows. if i use service A, i might oauth with my google login. if i use service B, i might oauth with my facebook login. but what if i want to be auth’d into both service A and service B using single auth step AKA single sign on. i’m lazy and i don’t want to use different oauth flows for each service. or maybe i’m a big corp and i want to centralize IT auth flows

OAuth, however, is not designed for single sign on scenarios (please correct me if i’m wrong!)

saml

that’s what SAML addresses! Implementing SAML for a web app is similar to OAuth in that identity is being delegated the auth to a third party, but in this case that third party is a specific entity known as an “Identity Provider” (IDP).

the responsibility of an identity provider is to grant a user access to multiple cool web apps, not just the one COOL WEB APP. the way this works is that each of those web apps have a trust relationship with the identity provider. so first trust is established with the IDP and that trust and then used to gain access to the related services. that’s basically single sign on in a nutshell.

the user signs into a single service (the identity provider) and that service has a trust relationship with N services. The user can then log into N services (one of which is yours) all mediated through SAML. this is why i believe someone came up with the fancy $100 dollar phrase “federated identity”

Prompt

A function f is defined by the rule that f(n) = n if n < 3 and f(n)=f(n-1) + 2*f(n-2) + 3*f(n-3) if n >= 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process. Hint: for iteration, think about how you might code this using a for-loop in a language like Python.

Solution

The recursive form is easier to tackle – LISP’s probably do the best job of expressing recursive mathematical expressions due to the extremely minimal syntax.

(define (fn n)
  (if (< n 3)
      n
      (+
       (fn (- n 1))
       (* 2 (fn (- n 2)))
       (* 3 (fn ( - n 3)))
      ) 
   )
)

Here’s an (incomplete) expansion using substitution of a call to (fn 10). Each newline denotes the expanded expression of the previous. Note the crazy combinatoric explosion of having not one but three recursive calls in the body – this creates a huge tree of deferred addition and multiplication operations.

(fn 10)

(+ (fn 9) (fn 8) (fn 7))

(+
 (+ (fn 8) (fn 7) (fn 6))
 (+ (fn 7) (fn 6) (fn 5))
 (+ (fn 6) (fn 5) (fn 4)))

(+
 (+
  (+
   (+ (fn 7) (fn 6) (fn 5))
   (+ (fn 6) (fn 5) (fn 4))
   (+ (fn 5) (fn 4) (fn 3))
  )
  (+
   (+ (fn 6) (fn 5) (fn 4))
   (+ (fn 5) (fn 4) (fn 3))
   (+ (fn 4) (fn 3) (fn 2))
  )
  (+
   (+ (fn 5) (fn 4) (fn 3))
   (+ (fn 4) (fn 3) (fn 2))
   (+ (fn 3) (fn 2) (fn 1))
  )
 )
 (+
  (+
   (+ (fn 6) (fn 5) (fn 4))
   (+ (fn 5) (fn 4) (fn 3))
   (+ (fn 4) (fn 3) (fn 2))
  )
  (+
   (+ (fn 5) (fn 4) (fn 3))
   (+ (fn 4) (fn 3) (fn 2))
   (+ (fn 3) (fn 2) (fn 1))
  )
  (+
   (+ (fn 4) (fn 3) (fn 2))
   (+ (fn 3) (fn 2) (fn 1))
   (+ (fn 2) (fn 1) (fn 0))
  )
 )
 (+
  (+
   (+ (fn 6) (fn 5) (fn 4))
   (+ (fn 5) (fn 4) (fn 3))
   (+ (fn 4) (fn 3) (fn 2))
  )
  (+
   (+ (fn 5) (fn 4) (fn 3))
   (+ (fn 4) (fn 3) (fn 2))
   (+ (fn 3) (fn 2) (fn 1))
  )
  (+
   (+ (fn 4) (fn 3) (fn 2))
   (+ (fn 3) (fn 2) (fn 1))
   (+ (fn 2) (fn 1) (fn 0))
  )
 )
)
...

Eventually, this long recursive process bottoms out at the base case when we reach (fn 2), (fn 1), and (fn 0) since none of those invocations will reach the recursive section of the procedure. For example, (fn 2) will return 2 since 2 < 3. These values will play an important role in developing the iterative solution.

Iterative Form

There’s a few ways to think about this problem to get an intuition about what the iterative form might look like. One way is to consider a similar problem such as the fibonacci sequence.

Fibonacci Sequence

Consider a similar mathematical expression such as the fibonacci sequence expressed in scheme as a recursive procedure.

(define (fib n)
  (if (< n 3)
      1
      (+ (fib (- n 1)) (fib (- n 2)))))

It’s simpler since there aren’t additional multiplication operations and you’re only dealing with two recursive procedures in the body instead of 3, but it exhibits the same pattern of process growth (exponential expansion followed by contraction).

(fib 5)

(+ (fib 4) (fib 3))

(+ (+ (fib 3) (fib 2)) (fib 3))

(+ (+ (+ (fib 2) (fib 1)) (fib 2)) (fib 3))

...

In the iterative form, you compute the next result using two values you currently have. You accumulate the answer from bottom up.

Here’s an example in scheme:

(define (fn n)
  (define (iter x a b)
    (if (> x n)
        a
        (iter (+ x 1) b (+ a b))))
  (if (< n 2) 1 (iter 2 1 1)))

a represents n - 2 and b represents n - 1. If we’re dealing with an n that’s less than 2, return 1. Otherwise kick off the recursive process with (iter 2 1 1). In each step, we compute the next result (+ a b) and feed that into our next recursive call as the new b.

There’s a few key insights from this iterative fibonacci definition:

1. You start with two values and you use them to compute the next value. As the computation evolves, so do the two values you’re holding at any given point.
2. Each step contains all the state you need to compute the next recursive step – there are no deferred operations
3. Some notion of a “base case” is still necessary for knowing when to stop the accumulation. In this example we use x and we stop when x is greater than the initial argument to the fibonacci function.

Back to the problem

The fibonacci definition has a key trait in common with our problem. The current result based on n is based on computation using the last three results (instead of the two by fibonacci). In fact, they’re so similar that if you squint you might see the iterative form of our problem!

(define (fn n)
  (define (iter x a b c)
    (if (> x n)
        c
        (iter (+ x 1) b c (+ (* 3 a) (* 2 b) c))))
  (if (< n 3) n (iter 3 0 1 2)))

Unlike our fibonacci problem, we need to perform both addition and multiplication (+ (* 3 a) (* 2 b) c) in order to generate the next result. This is what moves the computation along. With fibonacci, there’s just an addition (+ a b) that gets computed as the new next value – but the same underlying pattern applies. Compute the next value, shift all three numbers forward and repeat.

Commentary

We got this problem on the first day of David Beazley’s SICP course and it completely destroyed my brain when I initially attempted to come up with the iterative solution to this.

The new syntax combined with the noise from all the additional computation in the recursive function made it very challenging. I didn’t really have an AHA moment to this until David shared his solution with us and I only realized the connection to fibonacci when I set out to write this post and revisit my understanding of the exercise.

I think this is a great problem in terms of noticing this tension between simplicity and beauty of recursive procedure definitions and their performance. You have this simple definition that grows wildly during runtime. Then you go forth and optimize it so that it doesn’t accumulate on the stack but get a far less intuitive looking definition as a result. There’s also the fun challenge of porting a recursive definition to an iterative one and noticing some of the difficulties in coming up with the right base cases. It’s really easy to make off by one errors with these problems and it’s not immediately obvious why the results are wrong until you go back to trace the mathematical definitions manually which can be tedious.