Sachverhalt:
A.
In der Nacht vom 11. auf den 12. Februar 2006 brannte das Restaurant Q._ in U._. Die Staatsanwaltschaft des Kantons Bern erhob am 3. März 2015 Anklage gegen Z._ wegen Brandstiftung und Gehilfenschaft zum Betrug. Das Kantonale Wirtschaftsstrafgericht sprach Z._ am 18. Januar 2016 vom Vorwurf der Gehilfenschaft zum Betrug frei und verurteilte ihn wegen Brandstiftung zu einer bedingten Freiheitsstrafe von 22 Monaten. Gleichzeitig befand es über die Zivilklage der Gebäudeversicherung des Kantons Bern. Dagegen erhoben Z._, die Staatsanwaltschaft und die Gebäudeversicherung des Kantons Bern Berufung.
B.
Das Obergericht des Kantons Bern erklärte Z._ am 15. September 2017 der Brandstiftung und der Gehilfenschaft zum Betrug schuldig. Es bestrafte ihn mit einer bedingten Freiheitsstrafe von 19 Monaten. Gleichzeitig hiess das Obergericht die Zivilforderungen der Gebäudeversicherung des Kantons Bern in der Höhe von Fr. 775'000.-- gut.
C.
Z._ führt Beschwerde in Strafsachen. Er beantragt, er sei freizusprechen. Ihm sei eine Genugtuung von mindestens Fr. 5'000.-- sowie eine Aufwandsentschädigung in der Höhe von Fr. 1'000.-- zulasten des Kantons Bern zuzusprechen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Für das bundesgerichtliche Verfahren sei ihm die unentgeltliche Rechtspflege und Verbeiständung zu gewähren.
D.
Das Obergericht und die Generalstaatsanwaltschaft des Kantons Bern verzichten auf eine Vernehmlassung. Die Gebäudeversicherung des Kantons Bern beantragt, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Z._ replizierte.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt eine unvollständige und willkürliche Sachverhaltsfeststellung sowie eine Verletzung des Anspruchs auf rechtliches Gehör.
1.2.
1.2.1. Das erstinstanzliche Gericht erachtete es als erwiesen, dass Y._ und der Beschwerderführer am 11. Februar 2006 in das alte Restaurant Q._ gegangen seien und sich vergewissert hätten, dass dort keine Menschen anwesend seien. Sie hätten dann in einem Zimmer im ersten Stock eine Matratze mit Alkohol übergossen und mit Hilfe eines Feuerzeugs versucht, diese zu entzünden, was ihnen jedoch aufgrund der tiefen Temperaturen misslungen sei. Sie hätten es so aussehen lassen wollen, als sei der Brand von Obdachlosen verursacht worden. Ihnen sei bewusst gewesen, dass sich zu diesem Zeitpunkt im Restaurant noch teilweise gefüllte Gasflaschen befunden hätten. Daraufhin hätten Y._ und der Beschwerdeführer das Gebäude verlassen. Als dann die Q._ immer noch nicht gebrannt habe, habe der Beschwerdeführer seinen mobilen Gasofen, den er zu einem früheren Zeitpunkt in seinem Chalet geholt habe, im vorerwähnten Zimmer platziert und in Betrieb genommen. Damit habe er das Restaurant letztlich in Brand gesetzt. Y._ habe nicht versucht, den Beschwerdeführer davon abzuhalten, sondern habe auf diesen vor dem Gebäude gewartet.
1.2.2. Zur Beteiligung des Beschwerdeführers am Brand des Restaurants Q._ befasst sich die Vorinstanz in ihrem eigenen Urteil zunächst mit den Aussagen des Mitbeschuldigten Y._. Dieser habe anlässlich seiner ersten Einvernahme erklärt, dass der Beschwerdeführer, welcher wie er auf dem Campingplatz gewohnt habe, sich ständig über finanzielle Probleme beklagt habe. Er habe ihm deshalb gesagt, dass X._ bereit wäre, Fr. 80'000.-- für den Brand des alten Restaurants zu bezahlen; der Beschwerdeführer habe die Idee des Brandes angenommen. Y._ habe im Vorverfahren sowohl in seiner ersten Einvernahme als auch in den darauffolgenden das Vorgehen und die Beteiligung des Beschwerdeführers an der Brandlegung geschildert. Im Rahmen der erstinstanzlichen Hauptverhandlung habe Y._ seine bisherigen Aussagen grundsätzlich bestätigt, obwohl er auf Fragen nach Details beim Vorgehen häufig nicht mehr genaue Angaben habe machen können. Anlässlich der Berufungsverhandlung habe Y._ die Aussage verweigert. Die Aussagen von Y._ zur Beteiligung des Beschwerdeführers seien zusammenfassend konstant, plausibel, stimmig, detailliert, nachvollziehbar und damit glaubhaft. Dass dessen Aussagen im Zusammenhang mit dem Gasofen Ungenauigkeiten und Widersprüche enthalten würden, ändere daran nichts. Auch wenn Y._ offensichtlich darauf bedacht gewesen sei, seine eigene Rolle so zurückhaltend als möglich darzustellen, habe er dennoch nicht den Eindruck erweckt, X._ und den Beschwerdeführer zu Unrecht zu belasten oder deren Rolle überzubewerten.
Die Vorinstanz setzt sich sodann mit den Aussagen von D._, E._, C._, F._, G._, H._ und X._ auseinander. Sie hält fest, dass Y._ im Laufe der Zeit zahlreiche Personen über die Brandlegung informiert habe, dies - gemäss seinen eigenen Aussagen - weil er ein "blöder Prolet" sei. Dabei würden sich alle Schilderungen mehr oder weniger ähneln. Zumindest gegenüber seinem Vater (C._), D._ und H._ habe Y._ erwähnt, dass er den Brand zusammen mit dem Beschwerdeführer gelegt habe. Der Auftrag zur Brandlegung sei gemäss den Schilderungen mehrheitlich von X._ erteilt worden und stets sei es dabei um Geld gegangen, welches versprochen worden sei (Fr. 80'000.--, gemäss D._ Fr. 60'000.--). Auch von der Matratze und dem "Pennerlager" sei regelmässig die Rede gewesen. Bloss die Aussage von X._ passe überhaupt nicht ins Bild. Y._ habe also schon kurz nach dem Brand gegenüber mehreren Personen erwähnt, er habe diesen zusammen mit dem Beschwerdeführer gelegt. Entgegen den Ausführungen der Verteidigung sei es also nicht so gewesen, dass er die Beteiligung des Beschwerdeführers erst dann ins Spiel gebracht habe, als die ganze Sache bereits aufzufliegen drohte. Eine bereits damals erfolgte falsche Beschuldigung des Beschwerdeführers durch Y._ (um sich selber zu entlasten) mache keinen Sinn, zumal die ganze Geschichte ja erst aufgrund eines unvorhersehbaren Streits von X._ mit G._ aufgeflogen sei. Wäre es nach Y._ gegangen, wäre sie für immer verborgen geblieben. Es sei folglich schleierhaft, weshalb Y._ den Beschwerdeführer bereits in den Jahren 2006 bis 2009 zu Unrecht hätte belasten sollen. Den Akten sei auch kein Anlass für eine Falschbezeichnung aus Feindschaft zu entnehmen. In diesem Sinne erscheine der vom Beschwerdeführer erwähnte "Jugosturm" jedenfalls nicht besonders dramatisch gewesen zu sein. Damit stehe fest, dass Y._ nicht erst gegenüber den Strafverfolgungsbehörden, sondern auch gegenüber zahlreichen Drittpersonen die Beteiligung des Beschwerdeführers an der Brandstiftung erwähnt habe. Dies sei zu einem Zeitpunkt geschehen, als noch niemand damit gerechnet habe, dass die ganze Geschichte aufliegen könnte. Auch unter diesem Aspekt sei auf die glaubhaften Aussagen von Y._ abzustellen.
Die Vorinstanz erwägt weiter, dass auch die Aussagen und Reaktionen des Beschwerdeführers selbst keine Zweifel an dessen Beteiligung an der Brandstiftung offen lassen würden. Als er mit dem Vorwurf von Y._ konfrontiert worden sei, habe er sich emotionslos verhalten. Die Frage, ob er auf Y._ wütend sei, habe er verneint. Stattdessen habe er gesagt, er sei über ihn enttäuscht. Würde Y._ ihn zu Unrecht belasten, wäre - so die Vorinstanz - eine andere Gefühlsregung zu erwarten. Daneben seien die Aussagen des Beschwerdeführers auch inhaltlich bezeichnend. So habe er anlässlich seiner ersten Einvernahme ohne zu zögern und ohne gross zu überlegen genauestens ausgeführt, wie er den sieben Jahre zuvor liegenden Tag des Brandes verbracht habe. So habe er beispielsweise gesagt, am Niveauventil an der Hinterachse seines Lastwagens gearbeitet zu haben. Dieser Umstand lasse den Beschwerdeführer verdächtig erscheinen und lege die Vermutung nahe, dass es sich für ihn nicht um einen beliebigen Tag gehandelt habe. Daneben falle auf, dass der Beschwerdeführer unverfängliche Fragen kompliziert und ausführlich beantwortet habe, als ob er auf sicherem Terrain bleiben möchte. Darüber hinaus erstaune, dass er anlässlich der ersten Befragung keine Angaben über das Schicksal seines Gasofens habe machen können, sich jedoch später bei der Staatsanwaltschaft sehr genau daran erinnert habe, warum sich dieser nicht mehr in seinem Chalet befunden haben soll und entsorgt worden sei. Wenn seine Freundin I._ wirklich Angst vor dem Ofen gehabt hätte und dies der Grund für die Entsorgung gewesen wäre, wäre eine entsprechende Aussage des Beschwerdeführers von Anfang an zu erwarten gewesen. Darüber hinaus würden auch weitere Umstände für eine Tatbeteiligung des Beschwerdeführers sprechen. So sei es schwer vorstellbar, dass ausgerechnet der Beschwerdeführer nicht von der Täterschaft von Y._ gewusst haben soll, wo doch zahlreiche andere Bewohner des Campingplatzes darüber informiert gewesen seien. Der Beschwerdeführer bestreite auch nicht, zum Zeitpunkt des Brandes mit derjenigen Person - Y._ - zusammen gewesen zu sein, welche zugegebenermassen an der Brandstiftung beteiligt war. Darüber hinaus sei auffällig, dass Y._ anlässlich seiner ersten Einvernahme nur darauf hingewiesen habe, dass auf dem Campingplatz J._ mit einem Gasofen heize. Als Platzwart hätte ihm aber bewusst sein müssen, dass auch der Beschwerdeführer einen solchen Ofen besass. Aus heutiger Sicht sei klar, weshalb Y._ dies verschwiegen habe. Als weiteren Punkt trägt die Vorinstanz dem Umstand Rechnung, dass auch I._ sich anlässlich der Befragung durch die Staatsanwaltschaft sehr gut an Jahre zurückliegende Gegebenheiten in der Brandnacht erinnern konnte. Zudem habe sie keine Unmutsbezeugungen geschildert, obwohl der Beschwerdeführer, mit welchem sie vor der Einvernahme noch gesprochen habe, von Y._ angeblich zu Unrecht einer Straftat bezichtigt worden sein soll. Schliesslich sei auf eine an X._ adressierte Rechnung des Beschwerdeführers hinzuweisen. Diese sei angeblich am 16. Oktober 2008 für "Kieslieferung und Abbruch Seerose" ausgestellt worden. Warum der Beschwerdeführer mehr als zwei Jahre nach dem Brand und dem Wegräumen des Restaurants Q._ eine Rechnung gestellt haben soll, sei angesichts seiner steten finanziellen Probleme nicht nachvollziehbar. Dass der Beschwerdeführer es mit dem Antwortschreiben von X._ bewenden liess und keine Inkassomassnahmen ergriff, sei umso erstaunlicher. Es dränge sich somit der Schluss auf, dass die Rechnung keinen realen Hintergrund habe (Urteil, S. 19 ff.).
1.3. In Bezug auf Y._ macht der Beschwerdeführer zusammengefasst geltend, dass dieser über die verschiedenen Einvernahmen hinweg widersprüchliche Angaben gemacht habe. Entgegen der Auffassung der Vorinstanz sei dessen Darstellung deshalb weder konstant noch glaubhaft. Darüber hinaus macht der Beschwerdeführer - unter anderem - geltend, dass die Vorinstanz die Aussagen der Mitbeschuldigten X._ und Y._ sowie von D._, H._ und C._, welche allesamt direkt oder indirekt vom Brand profitieren würden, einseitig als glaubhaft einstufe. Die Erklärungen von F._ und E._, die aus dem Brand keinen Vorteil hätten, würdige die Vorinstanz hingegen nicht. Diese hätten übereinstimmend berichtet, dass Y._ ihnen gegenüber nicht erwähnt habe, dass der Beschwerdeführer an der Brandstiftung auch beteiligt gewesen sein soll. Die Vorinstanz erkläre nicht, weshalb der Inhalt dieser Zeugenaussagen nicht in die Beweiswürdigung einfliessen solle. Dies stelle sowohl eine willkürliche Beweiswürdigung als auch eine Verletzung der Begründungspflicht dar.
1.4.
1.4.1. Der Anspruch auf rechtliches Gehör (<ref-law>) verlangt, dass die Justizbehörde die Vorbringen der Parteien auch tatsächlich hört, prüft und in der Entscheidfindung berücksichtigt; daraus folgt insbesondere die Verpflichtung der Behörde, ihren Entscheid ausreichend und nachvollziehbar zu begründen (Urteil 1C_393/2018 vom 14. Dezember 2018 E. 3.1 mit Hinweisen, zur Publikation bestimmt).
1.4.2. F._ erklärte am 23. Juni 2014 als Zeuge, Y._ habe ihm nach einem feuchtfröhlichen Abend im August 2006 gesagt, die Q._ angezündet zu haben. Er habe von Y._ erfahren, dass vier Leute davon gewusst hätten, involviert oder anwesend gewesen seien. Y._ habe gemeint, man könne ihm nichts anhaben, da es Aussage gegen Aussage sei. Damals habe ihm Y._ keine Details genannt (kantonale Akten, pag. 323). Ebenfalls als Zeuge sagte E._ am 19. Mai 2014 aus, dass ihm Y._ an einem sommerlichen Tag auf einem Boot auf dem See erklärt habe, dass es schliesslich er gewesen sei, der die Q._ angezündet habe. X._ schulde ihm deshalb noch Fr. 80'000.-- (kantonale Akten, pag. 287).
Die Vorinstanz beschränkt sich darauf, festzuhalten, dass ein Teil der Zeugen bzw. der Mitbeschuldigten eine Beteiligung des Beschwerdeführers bestätigen würden. Dass ein Teil dieser Zeugen angaben, von Y._ erfahren zu haben, dass Letzterer das Restaurant Q._ selber angezündet haben soll, lässt die Vorinstanz unerwähnt. Sie legt auch nicht dar, weshalb sie nicht auf die Aussagen von F._ und E._ abstellt. Dies ist aber unerlässlich, zumal die Darstellung dieser Zeugen der Feststellung der Vorinstanz, wonach der Brand nicht von Y._, sondern vom Beschwerdeführer verursacht worden sein soll, widerspricht. Die Vorinstanz kommt ihrer Begründungspflicht in diesem Punkt nicht nach und verletzt den Anspruch des Beschwerdeführers auf rechtliches Gehör. Die Sache ist bereits aus diesem Grund an die Vorinstanz zurückzuweisen, damit diese den Sachverhalt unter Einbezug sämtlicher Zeugenaussagen neu würdigt.
2.
2.1. Der Beschwerdeführer macht zudem geltend, er habe am 13. September 2017 die Wiederaufnahme der Parteiverhandlung und die erneute Einvernahme von K._ sowie von L._ beantragt. Die Vorinstanz habe dies in Verletzung seines Anspruchs auf rechtliches Gehör verweigert (Beschwerde, S. 18 f.)
2.2. Der Beschwerdeführer beantragte am 4. Mai 2017, dass K._ anlässlich der Berufungsverhandlung als Zeugin zu befragen sei. X._ habe dieser in einem "lockeren Gespräch" offenbart, dass der Brand auf seine Initiative hin passiert sei und solche "Sachen" nur mit Ausländern zu bewerkstelligen seien. Als Verantwortlichen für die Brandstiftung habe X._ eine Person mit einem "Balkan-Namen" erwähnt. Durch die Vorinstanz zur Vernehmlassung eingeladen, unterstützten die Staatsanwaltschaft und die Privatklägerinnen diesen Beweisantrag. X._ sprach sich hingegen gegen die Zeugeneinvernahme aus. Am 13. Juni 2017 hiess die Vorinstanz den Beweisantrag des Beschwerdeführers gut. Die Berufungsverhandlung und die Einvernahme von K._ erfolgten am 12. September 2017. Am 13. September 2017 stellte die Verteidigerin des Beschwerdeführers den Antrag, die Parteiverhandlung sei wieder aufzunehmen. K._ und L._ seien (erneut) als Zeugen einzuvernehmen. Zur Begründung führte sie aus, L._ habe ihr am 13. September 2017 vorab telefonisch und danach mittels E-Mail mitgeteilt, am Vortag einen Anruf von K._ erhalten zu haben. Letztere habe ihm eröffnet, aus Angst vor X._ als Zeugin nicht die Wahrheit gesagt zu haben. Die Vorinstanz lehnte die Anträge des Beschwerdeführers mit Beschluss vom 14. September 2017 ab. Sie begründete dies damit, dass keine Mängel in der Beweiserhebung vorliegen würden und der Fall spruchreif sei. Am 15. September 2017 eröffnete die Vorinstanz das Urteil.
2.3. Nach Abschluss der Parteiverhandlung zieht sich das Gericht zur geheimen Urteilsberatung zurück (<ref-law>). Ist der Fall noch nicht spruchreif, entscheidet es, die Beweise zu ergänzen und die Parteiverhandlung wieder aufzunehmen (<ref-law>). K._ bestätigte anlässlich ihrer Befragung nicht, dass X._ ihr als Verantwortlichen für die Brandstiftung eine Person mit einem "Balkan-Namen" genannt habe. Nachdem Hinweise bestehen, dass K._ allenfalls eine Falschaussage gemacht haben könnte und der Beschwerdeführer keinen ausländischen Namen trägt, konnte der Fall am 14. September 2017 - entgegen der Auffassung der Vorinstanz - nicht als spruchreif angesehen werden. Die Sache ist auch aus diesem Grund zur Beweisergänzung und zu neuer Entscheidung an die Vorinstanz zurückzuweisen. Es erübrigt sich damit, auf die weiteren Rügen des Beschwerdeführers einzugehen.
3.
Die Beschwerde ist gutzuheissen. Der angefochtene Entscheid ist - soweit er den Beschwerdeführer betrifft - aufzuheben und die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen.
Für das bundesgerichtliche Verfahren sind die Kosten der unterliegenden Partei, jedoch nicht dem Kanton, aufzuerlegen (Art. 66 Abs. 1 und 4 BGG). Der Beschwerdeführer hat Anspruch auf eine angemessene Parteientschädigung zulasten des Kantons Bern und der Beschwerdegegnerin 2 (<ref-law>). Diese ist praxisgemäss der Rechtsvertreterin auszurichten. Das Gesuch des Beschwerdeführer um unentgeltliche Rechtspflege und Verbeiständung wird damit gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Das Urteil des Obergerichts des Kantons Bern vom 15. September 2017 wird, soweit es den Beschwerdeführer betrifft, aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Der Beschwerdegegnerin 2 werden Gerichtskosten von Fr. 1'500.-- auferlegt.
3.
Die Parteientschädigung von Fr. 3'000.-- an die Vertreterin des Beschwerdeführers, Rechtsanwältin Clivia Wullimann, tragen je zur Hälfte der Kanton Bern und die Beschwerdegegnerin 2 unter solidarischer Haftung.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Bern, 2. Strafkammer, schriftlich mitgeteilt.
Lausanne, 21. März 2019
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Moses