Overview
Every email address belongs to a domain, the part after the @, like yourbank.com. SPF (Sender Policy Framework) lets the people who run a domain publish a public list of the computers allowed to send mail in its name. Whoever receives a message can check the sender against that list. It is the oldest of the three standard checks, and one of the results Sieve reads when it evaluates your mail.
How SPF works
Anyone can write any name on the return address of a paper envelope. Email has the same problem: the “From” line on a message is just text, and nothing stops a sender from typing someone else's address into it.
SPF attacks the problem from the delivery side. When a message arrives, the receiving service looks up the sending domain's published server list and checks whether the server that actually delivered the message is on it. On the list, SPF passes. Not on the list, SPF fails: the message did not travel a route the domain owner approved.
One subtlety worth knowing: a message carries two sender addresses, the “From” line you read and a behind-the-scenes delivery address on the envelope. SPF checks the envelope address only. Connecting the two is the job of DMARC.
SPF checks who delivered the message, not the name on the “From” line. Connecting those two is DMARC's job.
What a failure means
A hard SPF failure says the delivering server was not on the domain's approved list. Sometimes that is exactly what it looks like: someone unauthorized sending mail in the domain's name.
There are also innocent ways to fail. Forwarding is the classic one: when a message is forwarded, the forwarding server becomes the deliverer, and it is usually not on the original domain's list. A domain owner who forgot to list a new sending service produces the same result. That is why receiving services read SPF alongside the other checks rather than in isolation, and why DMARC exists to arbitrate.
What Sieve shows you
When Sieve files a message as Malicious and authentication is part of the reason, your dashboard names the failed check, and SPF is one of the names you will see. The message is filed under a label in your Gmail, never deleted, so you can always open it and judge for yourself.
If you know the sender is real, drag the message back to your inbox (or restore it from the dashboard). One correction restores the message and teaches your own filter about that sender.
History and sources
SPF grew out of a scattering of independent 2002 proposals for catching forged “From” addresses. In June 2003, Meng Weng Wong merged two of them, Reverse MX and the Designated Mailer Protocol, into a single draft on a new mailing list he started, spf-discuss, under the working name Sender Permitted From. As the community grew, the project was renamed Sender Policy Framework in 2004 (dmarcian's history of SPF).
The IETF published the first formal specification, RFC 4408, in April 2006, but only as an Experimental document: the IETF said at the time that it was publishing SPF “as is,” without consensus on the broader email authentication approach. It took until April 2014 for the IETF to publish RFC 7208, the standards-track version of SPF still in force today, which formally obsoletes RFC 4408.
Further reading: SPF, explained by Google