Proving software integrity using Trusted Execution Environment/ Secure enclave

[Megasupersaiyan]

Suppose I have an algorithm that performs some trivial task, such as checking that a specified URL contains a given nonce in its metadata. Is it possible to build this algorithm using something like a TEE/secure enclave/etc. such that I can generate a proof that my result was in fact produced by my unaltered (open-source) algorithm running on hardware following the secure protocol? If so, how long would such a proof be? Would it be possible to encode the proof into the Bitcoin blockchain so that someone could later verify it?

Edit: It seems that StarkNet claims to have solved this problem even without using any specialized hardware by rewriting trivial computational problems into easily verifiable zero-konwladge proofs[1]. Am I understanding their claims correctly, and if so do they have any merit?

[1] https://eprint.iacr.org/2018/046.pdf

[1714036201]

1714036201

[1714036201]

1714036201

[1714036201]

1714036201

[1714036201]

1714036201

[1714036201]

1714036201

[1714036201]

1714036201

[n0nce]

Weeell, let's take a step back here. First of all, I don't understand what you are trying to prove. That when requesting data from some URL some certain reply comes back?
Even if you were to prove that, the API / backend could always change - so you could at most prove that it did return said data at a certain point in time.
You also don't really need to publish that on the blockchain, instead simply send the proof to the people interested in said proof and call it a day.

You're also correct in that proving ownership or knowledge of something can be easily done using Zero-Knowledge Proof algorithms and no secure element is needed for that.

[Megasupersaiyan]

Weeell, let's take a step back here. First of all, I don't understand what you are trying to prove. That when requesting data from some URL some certain reply comes back?
Even if you were to prove that, the API / backend could always change - so you could at most prove that it did return said data at a certain point in time.
You also don't really need to publish that on the blockchain, instead simply send the proof to the people interested in said proof and call it a day.

Precisely, for the example case I want to prove that the URL contained a specific nonce at a certain point in time, publishing the proof to the blockchain would be the equivalent to timestamping, so that I can't be using a proof from last week to prove that the nonce was present yesterday, even if it is no longer there today.

You're also correct in that proving ownership or knowledge of something can be easily done using Zero-Knowledge Proof algorithms and no secure element is needed for that.

I suppose my question is more about what class of computational problems I can expect to have a zero-knowledge proof of knowledge, and how to determine the amount of data necessary to store such a proof.

For example, can you use the same strategy to formulate a zero-knowledge proof for the above example and also to prove that a result of a visual classification problem was calculated using a specific open-source neural net without modification?

[NotATether]

Is it possible to build this algorithm using something like a TEE/secure enclave/etc. such that I can generate a proof that my result was in fact produced by my unaltered (open-source) algorithm running on hardware following the secure protocol?

Yes, you can run it inside an Intel software enclave on the CPU, but this is only available on fairly recent Intel processors with the SGX instruction set, and AMD doesn't have an equivalent (and actually this instruction set was deprecated by Intel recently!) I am not aware of any wrapper library providing access to this instruction set though.

If so, how long would such a proof be? Would it be possible to encode the proof into the Bitcoin blockchain so that someone could later verify it?

That would depend on the ZK proof algo you are using. If you choose bulletproofs then the size is going to be "8 + 2 log n group elements and 5 scalars". Here, group elements represent elliptic curve points.

[n0nce]

I suppose my question is more about what class of computational problems I can expect to have a zero-knowledge proof of knowledge, and how to determine the amount of data necessary to store such a proof.

You can generally reduce a ton of stuff to a ZK proof. As for amount of data required, it really depends. I would guess it's too much to publish on the blockchain; but then again, you can obviously store a hash of it and publish the actual proof on GitHub, forum(s), website etc. and people can verify that they match.
Your proof will need to include some kind of timestamp though; if you rely solely on the blockchain for timestamping, you could also upload an old proof and pretend the server is still returning something that it doesn't anymore. So you need ZK proof of knowledge and time and merely use the blockchain as a persistent storage mechanism.

Also, if only a hash is persistently stored on the blockchain, while the data isn't, you could take down the data and the proof would be basically gone. So I don't really see the application of blockchain here. It's too expensive to store the proof and not suited to prove knowledge at time x (in your scenario -- because it's not you proving, not the server, but you're the one uploading the proof, right), so there's no real benefit of using it.

For example, can you use the same strategy to formulate a zero-knowledge proof for the above example and also to prove that a result of a visual classification problem was calculated using a specific open-source neural net without modification?

It should be possible, but not trivial for sure.

[Megasupersaiyan]

You can generally reduce a ton of stuff to a ZK proof. As for amount of data required, it really depends. I would guess it's too much to publish on the blockchain; but then again, you can obviously store a hash of it and publish the actual proof on GitHub, forum(s), website etc. and people can verify that they match.
Your proof will need to include some kind of timestamp though; if you rely solely on the blockchain for timestamping, you could also upload an old proof and pretend the server is still returning something that it doesn't anymore. So you need ZK proof of knowledge and time and merely use the blockchain as a persistent storage mechanism.

Also, if only a hash is persistently stored on the blockchain, while the data isn't, you could take down the data and the proof would be basically gone. So I don't really see the application of blockchain here. It's too expensive to store the proof and not suited to prove knowledge at time x (in your scenario -- because it's not you proving, not the server, but you're the one uploading the proof, right), so there's no real benefit of using it.

Ok, so let's look at a slightly more concrete example closer to what I have in mind:

1. I host an open source program online that reads a proof and outputs whether it is valid or invalid for a given protocol. The program then publishes a succinct proof of what was done to the Bitcoin blockchain, including the nonce of the last block as a timestamp.

2. I take a photo with a camera that uses an open source protocol for generating images that are provably unaltered. Images and proofs are again timestamped with the nonce of the latest block at the time the picture was taken. Proofs can be arbitrarily long.

3. I send the image to an open-source image classifying algorithm I host online. It outputs the contents of the image along with a timestamped proof to my program from step 1.

4. Program from step 1 validates the input proof, and publishes a succinct proof along with some aggregate signature that identifies each protocol used including its own to the blockchain.

5. Someone can later verify that at the time corresponding to the specified block, an unaltered image was taken that showed content X, only needing to trust the validity of the open-source protocols and nothing else, even if the original image and intermediate proofs no longer exist.


Is this feasible? What are my security risks (besides the magical camera in step 2)?