Bitcoin is already legal in many countries, see
Legality of bitcoin by country or territory for a list per country.
Some countries officially recognize Bitcoin:
Japan officially recognizes bitcoin and digital currencies as a "means of payment that is not a legal currency"
Others declared it "not illegal":
As of November 2016 declared, bitcoins are "not illegal" according to the Federal Tax Service of Russia