Linear Least Squares with Monotonicity Constraint

Let $L$ be an $n\times n+1$ matrix such that $$ L = \begin{pmatrix} -1 & 1 & 0 & ... &0 \\ 0 & -1 & 1 & ... &0 \\ & & \\ 0 & 0 & ...& -1 &1 \\ \end{pmatrix}$$

Then you can formulate this as a constrained least squares problem$$\min_{x}||Ax-b||^2\ s.t. Lx \geq 0$$

Your idea to reformulate the problem so that the variables are $x_0$ and $y_i = x_i - x_{i-1}$ for $i =1, \ldots, n$ will work. Let $y$ be the vector whose components are $x_0, y_1, \ldots, y_n$ and define $$ M = \underbrace{\begin{bmatrix} 1 & 0 & \cdots & 0 \\ 1 & 1 & \cdots & 0 \\ \vdots & & & \vdots \\ 1 & 1 & \cdots & 1 \end{bmatrix}}_{(n+1)\times(n+1)}. $$

Notice that $M y = x$. Expressed in terms of $y$, your optimization problem is to minimize $\| AM y - b \|^2$ subject to the constraint that $y_i \geq 0$ for $i = 1, \ldots, n$. In this reformulated problem, the optimization variable is the vector $y$.