Solution:
1. Proof: Since $a_{n+1} = S_{n+1} - S_n = \frac{1}{8}(a_{n+1}+2)^2 - \frac{1}{8}(a_n+2)^2$, it follows that $8a_{n+1} = (a_{n+1}+2)^2 - (a_n+2)^2$. Therefore, $(a_{n+1}-a_n-4)(a_{n+1}+a_n) = 0$. Since $a_n \in \mathbb{N}^*$, we have $a_{n+1}+a_n \neq 0$, thus $a_{n+1}-a_n-4 = 0$. This implies $a_{n+1}-a_n = 4$, therefore, the sequence $\{a_n\}$ is an arithmetic sequence.

2. From (1), we know $a_1 = S_1 = \frac{1}{8}(a_1+2)^2$, solving this gives $a_1 = 2$. Therefore, $a_n = 4n-2$, and $b_n = \frac{1}{2}a_n - 30 = 2n-31$. (Solving by two methods)

Method 1:
Given $b_n = 2n-31$, the first term $b_1 = -29$, and the common difference $d = 2$. Therefore, the sum of the first $n$ terms of $\{b_n\}$, $s_n = n^2 - 30n = (n-15)^2 - 225$. Thus, when $n = 15$, $s_n = -225$ is the minimum.

Method 2:
From $\begin{cases} 2n-31\leq 0 \\ 2(n+1)-31\geq 0 \end{cases}$, we get $\frac{29}{2} \leq n \leq \frac{31}{2}$. Since $n \in \mathbb{N}^*$, $n = 15$. Therefore, the first 15 terms of $\{a_n\}$ are negative, and the subsequent terms are positive. Thus, $S_{15}$ is the minimum. Given $b_1 = -29$, we have $S_{15} = \frac{15(-29+2\times15-31)}{2} = -225$.

Therefore, the minimum value of the sum of the first $n$ terms of the sequence $\{b_n\}$ is $\boxed{-225}$.

Solution:
$(1)$ Proof: Since $a_{n+1}$
$=S_{n+1}-S_{n}$
$= \frac {1}{8}(a_{n+1}+2)^{2}- \frac {1}{8}(a_{n}+2)^{2}$,
$\therefore 8a_{n+1}=(a_{n+1}+2)^{2}-(a_{n}+2)^{2}$,
$\therefore (a_{n+1}-a_{n}-4)=0$,
Since $a_{n} \in \mathbb{N}^*$, $\therefore a_{n+1}+a_{n} \neq 0$,
$\therefore a_{n+1}-a_{n}-4=0$.
Thus, $a_{n+1}-a_{n}=4$, $\therefore$ the sequence $\{a_n\}$ is an arithmetic sequence.
$(2)$ From $(1)$, we know $a_{1}=S_{1}= \frac {1}{8}(a_{1}+2)^{2}$, solving this gives $a_{1}=2$. Therefore, $a_{n}=4n-2$,
$b_{n}= \frac {1}{2}a_{n}-30=2n-31$, (The following uses two methods to solve)
Method one:
From $b_{n}=2n-31$, we get: the first term $b_{1}=-29$, common difference $d=2$
$\therefore$ The sum of the first $n$ terms of the sequence $\{b_n\}$ is $s_{n}=n^{2}-30n=(n-15)^{2}-225$
$\therefore$ When $n=15$, $s_{n}=-225$ is the minimum;
Method two:
From $\begin{cases} 2n-31\leqslant 0 \\ 2(n+1)-31\geqslant 0 \end{cases}$, we get
$\frac {29}{2}\leqslant n\leqslant \frac {31}{2}$. Since $n \in \mathbb{N}^*$, $\therefore n=15$,
$\therefore$ The first $15$ terms of $\{a_n\}$ are negative, and the subsequent terms are all positive.
$\therefore S_{15}$ is the minimum. Also, since $b_{1}=-29$,
$\therefore S_{15}= \frac {15(-29+2\times15-31)}{2}=-225$

Thus, the minimum value of the sum of the first $n$ terms of the sequence $\{b_n\}$ is $\boxed{-225}$.