I have overviewed last @karl’s works on Plasma, but have not seen the solution. Perhaps, @karl is planning to commit the solution here, but it is still tagged “top secret”.
Also, we have discussed the O(1) solution in our workshop after the devcon4 and found history split issue: the plasma operator can forge queer chains and hide them from honest users. Users can easily prove the consistency and validity of the real chain offchain. But plasma operator can try to exit from a queer chain and it is not easy to expand history back onchain and find the defect.
I did not look at the problem intently, but now I see, that the complexity is about \log_2 M, where M is a number of transactions with the coin in the real chain from the deposit or checkpoint.
There is not so a huge number of challenges for coin used once per day (lesser than 9 steps for a year) and more complex problem for coin used every 5 minutes (17 steps for a year). The steps can be batched (for example, \times 8 for one request size and \div 3 for a number of requests).
Probably I missed the best solution. So, I have a question: have you got constant time challenges in your O(1) prime number plasma spec?