Sachverhalt:
A.
Die Bundesanwaltschaft erhob am 7. Oktober 2014 Anklage gegen X._ wegen qualifizierter Geldwäscherei und Falschbeurkundung. X._ soll zwischen 1999 und 2005 im Zusammenhang mit drei Infrastrukturprojekten der Stadt A._ (Projekte "B._", "C._" und "D._") diverse Banktransaktionen und Bargeldgeschäfte mit Geldern ausgeführt haben, die aus der Bestechung von ausländischen Amtsträgern stammen sollen.
B.
Das Bundesstrafgericht sprach X._ am 3. Juni 2015 frei, soweit es das Verfahren nicht infolge Verjährung einstellte.
C.
Die Bundesanwaltschaft führt Beschwerde in Strafsachen. Sie beantragt, das Urteil des Bundesstrafgerichts sei aufzuheben und die Sache an die Vorinstanz zurückzuweisen.

Erwägungen:
1.
1.1.
Hinsichtlich der Frage, ob in Bezug auf die dem Beschwerdegegner vorgeworfene Geldwäscherei eine taugliche Vortat vorliegt, hält die Vorinstanz fest, dass gemäss Anklage die Gesellschaften E._ und F._ gestützt auf fiktive Beratungsverträge Bestechungszahlungen auf Konten der Gesellschaften G._ und H._ getätigt hätten. Sowohl G._ als auch H._ seien auf I._ zurückzuführen, der lediglich als Intermediär und Strohmann anstelle der ausländischen Funktionäre, insbesondere J._, eingesetzt worden sei. Die Anklage gehe davon aus, dass die ausländischen Amtsträger an den betreffenden Vermögenswerten tatsächlich wirtschaftlich berechtigt gewesen seien und diese bereits mit den Überweisungen an G._ und H._ faktisch erlangt hätten.
Die Vorinstanz erwägt, dass Hinweise bestehen würden, wonach E._ und F._ I._ die in der Anklageschrift thematisierten Beträge zwecks Bestechung von Amtsträgern in A._ zukommen liessen. Es bestehe aber kein ausreichender Nachweis dafür, dass die betreffenden Amtsträger bereits mit den Überweisungen an G._ und H._ die Verfügungsgewalt über diese Gelder erlangt hätten. Das vorhandene Beweismaterial könne dahingehend interpretiert werden, dass E._ bzw. F._ die Dienste von I._ in Anspruch nahmen, weil er ihnen aufgrund seiner Verbindungen in der Politik dabei behilflich sein konnte, Kontakte mit den Entscheidträgern in den entsprechenden Projekten herzustellen und diese mit Bestechungszahlungen zu bedienen. Nach dieser Betrachtungsweise sei I._ auf Seiten der Bestecher (E._ bzw. F._) aufgetreten und nicht als ein auf Anweisung der Bestochenen handelnder Strohmann. Gehe man von diesem Ansatz aus, so sei die Verfügungsmacht über die entsprechenden Gelder bei I._, allenfalls bei E._ oder F._ gelegen. Der Übergang der Verfügungsmacht habe, wenn überhaupt, erst im Anschluss an die vom Beschwerdegegner organisierten Bargeldbezüge stattgefunden.
Die Vorinstanz führt weiter an, dass, sofern sich aus den Akten konkrete Anhaltspunkte für die Strohmanntheorie ergeben, sich diese auf die Person von J._ beziehen würden. Dieser habe erst Ende März 1999 das Amt des Stadtpräsidenten von A._ angetreten; der Beratervertrag zwischen E._ und G._ sei aber bereits am 20. November 1998 abgeschlossen worden. Es könne daher nicht angenommen werden, dass I._ von Beginn seiner angeblichen Beratertätigkeit für E._ an als Strohmann für J._ agiert habe. Auch würden keine konkreten Hinweise dafür bestehen, dass er zunächst für andere Hintermänner tätig gewesen sei. Wenn I._ aber nicht von Anfang an als Strohmann gehandelt habe, so sei es unwahrscheinlich, dass er dies zu einem späteren Zeitpunkt getan habe. Hinzu komme, dass das Ausschreibungsverfahren in Bezug auf das Projekt "B._" am 9. April 1998 durchgeführt worden sei. Der Vertrag zwischen E._ und dem Auftraggeber sei am 22. Juli 1998 unterschrieben worden. J._ habe folglich bei der Auftragsvergabe keine Rolle spielen können. Es sei nicht nachvollziehbar, welche Gegenleistung von J._ im bereits laufenden Projekt mittels Bestechungsgelder hätte erkauft werden können. Zusammenfassend sei nicht erstellt, dass die Vermögenswerte, mit welchen der Beschwerdegegner die ihm vorgeworfenen Handlungen vornahm, aus der Bestechung von Amtsträgern stammten. Wenn überhaupt seien diese für eine Bestechung bestimmt gewesen; es habe sich mithin um instrumenta sceleris gehandelt. Diese seien kein taugliches Geldwäschereiobjekt, weshalb der Tatbestand von Art. 305bis StGB nicht erfüllt sei.
1.2. Die Beschwerdeführerin bringt vor, dass durch die Aussonderung von Geldern an I._ E._ und F._ ihren Bestechungswillen manifestiert hätten, womit in Bezug auf den Tatbestand der aktiven Bestechung die Schwelle zum Versuch überschritten worden sei. Dieser Tatbestand sei zudem sowohl in der Variante des Anbietens und Versprechens als auch in derjenigen des Gewährens eines nicht gebührenden Vorteils erfüllt bzw. vollendet. Dies weil E._ und F._ wohl kaum Bestechungsgelder an einen Dritten überwiesen hätten, wenn nicht vorgängig mit den zu bestechenden Amtsträgern eine entsprechende Vereinbarung getroffen worden wäre. Darüber hinaus hätten E._ und F._ mit den Überweisungen an I._ bzw. G._ und H._ jeglichen Zugriff auf die betreffenden Gelder verloren. Das bestechende Unternehmen gehe in der Folge davon aus, dass die Bestechungsgelder gemäss Abrede auch in die formelle Verfügungsmacht des Bestochenen gelangen würden. Solange die Gelder auf dem Konto eines Intermediärs liegen würden, habe der Bestochene keinen formellen Zugriff auf die Vermögenswerte, obwohl er daran bereits der rechtmässige Eigentümer sei. Die Weiterleitung durch den Mittelsmann stelle nur noch den letzten notwendigen Schritt zur Überführung der Bestechungsgelder in die formelle Verfügungsmacht des Bestochenen dar. Im Hinblick auf die Vollendung der Gewährung von Bestechungsgeldern könne diesem Vorgang keine Bedeutung zukommen. Anders verhalte es sich bezüglich der Vollendung der passiven Bestechung in der Variante des Annehmens, zumal die Bestechungsgelder nach der Auszahlung an einen Intermediär sich materiell bereits in der Verfügungsmacht des Bestochenen befinden, es aber noch an einer Formalisierung dieser Verfügungsmacht fehle. Zusammenfassend ergebe sich, dass der Tatbestand der aktiven Bestechung in den Varianten des Versprechens, Anbietens und Gewährens eines nicht gebührenden Vorteils und derjenige der passiven Bestechung in der Form des Sich-versprechen-Lassens, noch nicht aber in der Variante des Annehmens, vollendet sei. Selbst wenn die Bestechung nur versucht worden sei, liege eine im Sinne des Geldwäschereitatbestandes taugliche Vortat vor.
Die Beschwerdeführerin macht zudem geltend, dass unter Umständen versuchte Geldwäscherei vorliegen könne, wenn Vermögenswerte, die noch nicht aus einem Verbrechen stammen, erst zu Bestechungszwecken bestimmt worden seien. Sollte das Bundesgericht nicht von vollendeter Geldwäscherei ausgehen, müsste daher zumindest versuchte Geldwäscherei bejaht werden.
1.3.
1.3.1. Die Beschwerdeführerin stützt ihre Auffassung, es liege eine vollendete Vortat vor, auf die Annahme, dass E._ bzw. F._ mit den zu bestechenden Amtsträgern eine entsprechende Vereinbarung abgeschlossen hätten, bevor sie die Überweisungen auf die Konten von G._ und H._ vornahmen. Die Vorinstanz stellt Derartiges nicht fest. Sie geht vielmehr davon aus, dass E._ und F._ die Dienste von I._ in Anspruch nahmen, um Kontakte mit den betreffenden Amtsträgern überhaupt knüpfen zu können. Auf die in diesem Zusammenhang stehende Rüge ist nicht einzutreten, zumal sich die Beschwerdeführerin in diesem Punkt von den verbindlichen Sachverhaltsfeststellungen der Vorinstanz entfernt (Art. 105 Abs. 1 BGG), ohne zu behaupten noch darzulegen, dass diese willkürlich seien.
1.3.2. Nach Art. 305bis Abs. 1 StGB (in der bis zum 31. Dezember 2015 geltenden Fassung) macht sich der Geldwäscherei strafbar, wer eine Handlung vornimmt, die geeignet ist, die Ermittlung der Herkunft, die Auffindung oder die Einziehung von Vermögenswerten zu vereiteln, die, wie er weiss oder annehmen muss, aus einem Verbrechen herrühren. Am Tatwerkzeug (instrumentum sceleris) ist Geldwäscherei nicht möglich, zumal dieses nicht aus einem Verbrechen herrührt (JÜRG-BEAT ACKERMANN, Geldwäscherei - Money Laundering, 1992, S. 241 f.).
Das Bundesgericht hat in <ref-ruling> E. 4 festgehalten, dass versuchte Geldwäscherei auch möglich ist, wenn die Vortat noch nicht begangen worden ist. Dass eine Vortat vorliegt, bei welcher die Versuchsstufe erreicht wurde, genügt indes alleine nicht, um Geldwäscherei zu bejahen. Auch in diesem Fall ist der Tatbestand nur dann erfüllt, wenn durch die strafbare Handlung illegale Vermögenswerte angefallen sind (CHRISTINE EGGER TANNER, Die strafrechtliche Erfassung der Geldwäscherei, 1999, S. 42 f.; JÜRG-BEAT ACKERMANN, a.a.O, S. 222) oder zumindest erwartet waren (vgl. hierzu MARTIN SCHUBARTH, Geldwäscherei - Neuland für das traditionelle kontinentale Strafrechtsdenken, in: Festschrift für Günter Bemmann, Baden-Baden 1997, S. 439). Die vorliegend zur Diskussion stehenden Vermögenswerte sind nicht das Ergebnis einer Bestechung, sondern nur Tatwerkzeug, was die Beschwerdeführerin nicht in Abrede stellt. Auch ist nicht erstellt, dass der Beschwerdegegner durch seine Handlungen die Wäsche des aus der Bestechung zu erwarteten Erlöses vorbereitete. Es kann daher weder von vollendeter noch von versuchter Geldwäscherei die Rede sein.
2.
2.1. Die Bundesanwaltschaft warf dem Beschwerdegegner in verschiedenen Fällen vor, er habe im Rahmen der Erfüllung seiner Dokumentationspflicht mit seinem Kürzel auf verschiedenen Auszahlungsbelegen bestätigt, dass K._ und L._ verschiedene Beträge bar erhalten hätten, obwohl er wusste, dass diese Personen nur vorgeschoben wurden, um den tatsächlichen Empfänger des Bargeldes nicht offenzulegen (Anklagevorwürfe 1.2.1.4, 1.2.1.5, 1.2.2.2, 1.2.2.3 und 1.2.2.4). Die Vorinstanz erwägt diesbezüglich, dass in der Anklageschrift nicht behauptet werde, dass K._ und L._ nicht physisch Geld entgegengenommen haben sollen. Eine solche Annahme sei auch nicht durch die Akten gestützt. Der Beschwerdegegner sei folglich auch in diesen Punkten freizusprechen.
2.2. Die Beschwerdeführerin rügt, die Vorinstanz habe den Sachverhalt in dieser Hinsicht willkürlich festgestellt. Es sei nicht K._ oder L._, sondern der Beschwerdegegner gewesen, der das Bargeld jeweils physisch entgegengenommen habe. Aus der Formulierung in der Anklageschrift ergebe sich in keiner Art und Weise, dass K._ und L._ das Bargeld physisch entgegen genommen haben sollen. Der Beschwerdegegner sei selber der tatsächliche Empfänger des Bargeldes gewesen.
2.3. Der Anklageschrift ist nur zu entnehmen, dass K._ und L._ vorgeschoben worden seien, um den tatsächlichen Empfänger des Bargeldes nicht offenzulegen. Dass sie das Geld nie in Empfang genommen haben sollen, wird in der Anklage nicht erwähnt. Genau dies wäre aber notwendig gewesen, um die von der Bundesanwaltschaft geforderte Verurteilung wegen Urkundenfälschung zu rechtfertigen. Der Freispruch des Beschwerdegegners vom Vorwurf der Urkundenfälschung verletzt kein Bundesrecht.
3.
Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Der unterliegenden Bundesanwaltschaft sind keine Kosten aufzuerlegen (Art. 66 Abs. 4 BGG). Dem Beschwerdegegner ist keine Entschädigung zuzusprechen, da ihm im bundesgerichtlichen Verfahren keine Umtriebe entstanden sind.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Es werden keine Kosten erhoben.
3.
Dieses Urteil wird den Parteien und dem Bundesstrafgericht, Strafkammer, schriftlich mitgeteilt.
Lausanne, 29. September 2016
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Moses