The key notion in service-oriented architecture is decoupling clients and providers of a service based on an abstract service description, which is used by the service broker to point clients to a suitable service implementation. A client then sends service requests directly to the service implementation. A problem with the current architecture is that it does not provide trustworthy means for clients to specify, service brokers to verify, and service implementations to prove that certain desired non-functional properties are satisfied during service request processing. An example of such non-functional property is access and persistence restrictions on the data received as part of the service requests. In this work, we propose an extension of the service-oriented architecture that provides these facilities. We also discuss a prototype implementation of this architecture and report preliminary results that demonstrate the potential practical value of the proposed architecture in real-world software applications.