You are breaking format rules. Normally when you use format Python looks for the following
"{" [field_name] ["!" conversion] [":" format_spec] "}"
So in your case "message" becomes a field_name, since { is before it and : after it. This obviously doesn't work. The .format() method is not meant to be used with complex, nested text structures.
One way is to use string.Template together with .substitute instead:
>>> tmpl = string.Template('{"message":"message_test", "subscription_info": {$subscription_info} }')
>>> tmpl.substitute(subscription_info=subscription_info)
'{"message":"message_test", "subscription_info": {{"endpoint":"xxx","keys":{"p256dh":"xxx","auth":"xxx"}}} }'
However it also isn't meant to be used with nested text structures.
Since you are using JSON then perhaps you should parse and serialize the JSON instead. This is the proper way to handle the problem:
>>> import json
>>> subscription_info = {"endpoint":"xxx","keys":{"p256dh":"xxx","auth":"xxx"}}
>>> send_data = {"message":"message_test", "subscription_info": subscription_info }
>>> json.dumps(send_data)
'{"subscription_info": {"endpoint": "xxx", "keys": {"auth": "xxx", "p256dh": "xxx"}}, "message": "message_test"}'
It is the cleanest and safest method.