Sachverhalt:
A.
Die Staatsanwaltschaft Zürich - Sihl erhob am 13. Oktober 2014 Anklage gegen X._ wegen Sachbeschädigung und mehrfacher Verletzung der Verkehrsregeln. Das Bezirksgericht Zürich erklärte X._ am 6. Januar 2015 der Verletzung von Verkehrsregeln (Art. 43 Abs. 3 SVG und Art. 36 Abs. 3 VRV) schuldig und bestrafte ihn dafür mit einer Busse von Fr. 200.--. Von den Vorwürfen der Sachbeschädigung und der Verletzung von Verkehrsregeln (Art. 44 Abs. 1 SVG und Art. 34 Abs. 3 VRV) sprach es ihn frei. Gegen dieses Urteil erhob die Staatsanwaltschaft Berufung und beantragte, X._ sei zusätzlich der Sachbeschädigung schuldig zu erklären.
B.
Das Obergericht des Kantons Zürich stellte am 25. August 2015 fest, dass das erstinstanzliche Urteil bezüglich den Verkehrsregelverletzungen in Rechtskraft erwachsen war und erklärte X._ zusätzlich der Sachbeschädigung schuldig. Es bestrafte ihn mit einer bedingten Geldstrafe von 15 Tagessätzen zu Fr. 140.-- und eine Busse von Fr. 200.--.
Das begründete Urteil wurde X._ am 27. Oktober 2015 zugestellt. Es war vom Gerichtsschreiber, nicht aber vom Vorsitzenden, unterschrieben.
C.
X._ führt Beschwerde in Strafsachen. Er beantragt, er sei vom Vorwurf der Sachbeschädigung freizusprechen. Der Beschwerde sei die aufschiebende Wirkung zu erteilen.
D.
Das Obergericht und die Oberstaatsanwaltschaft des Kantons Zürich verzichten auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Der Beschwerdeführer macht geltend, das Urteil des Obergerichts sei nicht ordnungsgemäss unterschrieben worden. Auch nachträglich sei ihm kein den Anforderungen von Art. 80 Abs. 2 StPO genügendes Urteil zugestellt worden. Der Entscheid leide an einem unheilbaren Mangel.
1.2. Nach Art. 80 Abs. 2 und 3 StPO ergehen Entscheide (ausser einfache verfahrensleitende Beschlüsse und Verfügungen) schriftlich und werden begründet; sie werden von der Verfahrensleitung sowie der protokollführenden Person unterzeichnet und den Parteien zugestellt. Bei der Unterschrift handelt es sich um ein Gültigkeitserfordernis (<ref-ruling> E. 2.3.3; Urteile 4A_20/2011 vom 11. April 2011 E. 6; 1B_608/2011 vom 10. November 2011 E. 2.3; 9C_511/2014 vom 26. September 2014 E. 3.3; DANIELA BRÜSCHWEILER, in: Donatsch/ Hansjakob/Lieber, Kommentar zur Schweizerischen Strafprozessordnung, 2. Aufl. 2014, N. 3 zu Art. 80 StPO).
Das dem Beschwerdeführer zugestellte Urteil trägt nur die Unterschrift des Gerichtsschreibers, nicht aber des Präsidenten. Es genügt den Anforderungen von Art. 80 Abs. 2 StPO nicht. Auch nachträglich wurde dem Beschwerdeführer kein Entscheid zugestellt, der den gesetzlichen Formvorschriften entsprechen würde. Der angefochtene Entscheid ist aufzuheben und zu neuer Eröffnung an die Vorinstanz zurückzuweisen.
2.
Für das bundesgerichtliche Verfahren sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Der Beschwerdeführer liess sich nicht anwaltlich vertreten, weshalb er keinen Anspruch auf eine Parteientschädigung hat. Er legt auch nicht dar, inwiefern besondere Umstände vorliegen, die eine Entschädigung rechtfertigen würden (vgl. <ref-ruling> E. 5b mit Hinweisen). Das Gesuch um aufschiebende Wirkung wird gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Der angefochtene Entscheid wird aufgehoben und zu neuer Eröffnung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer schriftlich mitgeteilt.
Lausanne, 31. Mai 2016
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Moses