I'll describe the standard Shamir trick adapted to the context of ECDSA signature verification. Dropping some indices, the computationally expensive part of it is computing
$$u\cdot G+v\cdot Q$$
where $u$ and $v$ are (we assume, strictly positive) integers, $G$ and $Q$ are Elliptic Curve points, and $+$ is point addition (which for simplification I consider a black box, which execution dominates the computational cost). Recall that by definition, $$u\cdot G=\underbrace{G+G+\ldots+G+G}_{u\text{ terms}}$$
Well note $\mathbin\|u\mathbin\|$ for the number of bits in integer $u$, that is $\left\lfloor\log_2(u)+1\right\rfloor$; same for $\mathbin\|v\mathbin\|$.
A common way of computing $u\cdot G$ is to
- set $R:=G$
- for bit $b$ copied from the binary representation of $u$, starting at index $\mathbin\|u\mathbin\|-1$ (the first bit on the right of the leftmost $1$ bit) down to $0$ (the rightmost bit)
- set $R:=R+R$
- if $b=1$, set $R:=R+G$
The basic way to compute $u\cdot G+v\cdot Q$ would be to compute $u\cdot G$, then $v\cdot Q$ by the same method, then add the two results. Shamir's trick improves on that:
- set $H:=G+Q$
- if $\mathbin\|u\mathbin\|>\mathbin\|v\mathbin\|$, set $R:=G$;
- else if $\mathbin\|u\mathbin\|<\mathbin\|v\mathbin\|$, set $R:=Q$;
- else (that is if $\mathbin\|u\mathbin\|=\mathbin\|v\mathbin\|$ ), set $R:=H$;
- for bit $b$ (resp. $c$) copied from the binary representation of $u$ (resp. $v$), with the representations of $u$ or $v$ left-padded with zeroes as necessary, at index from $\max(\mathbin\|u\mathbin\|,\mathbin\|v\mathbin\|)-1$ down to $0$
- set $R:=R+R$
- if $b=1$ and $c=0$, set $R:=R+G$
- (else) if $b=0$ and $c=1$, set $R:=R+Q$
- (else) if $b=1$ and $c=1$, set $R:=R+H$
This statement is nearly equivalent to the one given in this answer under the name Strauss-Shamir trick (when I know the trick as Shamir's). The variant I give avoids the need to know the group neutral, but requires $\max(u,v)>0$.
Correctness of standard point multiplication and Shamir's trick can be formally proven by induction.
For large random $u$ and $v$ of $k$ bits, the naive algorithm to compute $u\cdot G+v\cdot Q$ performs on average $\approx3k$ point additions, Shamir's trick reduces that to $\approx1.75k$, like 42% less (the cost benefit is lower, in large part because point doubling $R:=R+R$ is the fastest kind of point addition, and the one which gets most diminished). There are further improvements possible, e.g. grouping bits by two or slightly more, perhaps with "sliding window" when $b=0=c$.
Notice that in the context of signature verification, $u$, $v$, $G$ and $Q$ all are public, thus side channels (timing, power draw, emission, caches…) are not a security issue, as they are in signature generation.
I don't know the Strauss-Shamir trick of the question's other reference, but vaguely suspect that it further improves on this by sometime performing subtraction instead of addition, and/or is more compatible with a speedup technique for point addition.
