Según el DRAE procede del verbo "baratar" que es de origen incierto (como era de esperar, para la RAE todo es incierto).

Sin embargo existe la misma familia de palabras en italiano: "baratto" y "barattare" con el significado de 'cambio', 'cambiar' y Etimo.it la hace derivar de un griego PRATTEIN, 'negociar'. También existe una palabra inglesa con significado semejante: "barter".

A ver qué dice Coromines.

Para Coromines es también de origen incierto, aunque aventura alguna hipótesis. Que sea de origen prerromano y emparentado con el céltico *MRATOS ('engaño', 'traición'), de donde el irlandés medieval "brath" y el bretón "brat".

Parece que la mención más antigua en castellano es de 1155, como sustantivo y con el significado de 'fraude'.

A mí también la hipótesis celta me parece lo más probable porque:
1. PRA- no da "bar-" en castellano ni en italiano, y
2. el único pueblo prerromano que vivía tanto en Italia como en Hispania, fueron los celtas.