Demo of transaction proof for Polygon day at EthCC 19th of July

[Dominik1999]

Interactive talk with live proofs

At Polygon Day on the 19th of July, we have a Miden presentation scheduled. I want to show our core feature, client-side proving, in an interactive talk. That means the audience should create transaction proofs to show the speed of the Miden VM.

In an ideal world ...

In an ideal world, I would have a QR code for the people in the audience to scan. This would route the participants to a website similar to our Playground. The participants would see a screen with rudimentary account info and three buttons

• Prove
• Send
• Show

Every user would have an account_ID (we can grind them before) and, let's say, 100 MATIC. I can explain on stage that "clicking prove" triggers a transaction proof creating a note owning 10 MATIC. While it is proven on the mobile phone, we can show an animation.

Assuming it only takes 2 seconds to prove on a mobile (let's say iPhone 12), we can do it. Next would be for users to send those transaction proofs together with their notes.

On stage, we would show a simple list of all incoming proofs, and one after another, we can verify them and make a green hook if verified.

If users want, they can send notes anonymously or with their account ID. Verification must not be against a database, but it can check signatures or whatever we can do at this moment.

The Show-Button would show the proof to the user and maybe provide some background info.

Technical requirements

We need to have some things in place to be able to showcase this live and "bug" free:

1. Transaction proofs must be possible on mobile phones in a reasonable time (2s or less) in the browser
2. Users must be able to send the proofs without downloading software or logging in
3. There must be some proto-Miden Node that can verify transaction proofs even without having the full databases, so we need some mocked data there
4. We need laser sounds

[bobbinth]

This would be a cool demo indeed - but I'm thinking as written it would be quite difficult to pull off in the next 3 weeks. Though, maybe we can simplify somewhat. A few thoughts:

Proving on a mobile phone is not something that we've optimized, and it is likely to be much slower than 2 seconds for real transactions. We probably won't be able to prove more than $2^{13}$ cycles in 2 seconds on an iPhone 12 using BLAKE3. And if we wanted to use RPO (which we'd need to use for real transactions), we'd probably be able to do $2^{10}$ cycles.

For reference, our stretch goals for Falcon signature verification is $2^{15}$ cycles. So, we are probably looking at 30 - 60 second to prove a real transaction on an iPhone 12. Things which will bring this down quite a bit in the future are:

• Using multi-threading and/or WebGPU.
• Faster hash functions.
• General VM optimizations.

But we won't have any of these implemented by the 19th. So, I guess our options are:

1. Do proving on laptops - probably means we won't be able to make the demo interactive.
2. Prove simplified transactions - e.g., without signatures or using BLAKE3 hash function.

The latter may happen anyway as I'm not sure we'll have Flacon signature implemented/optimized/integrated by the 19th anyway.

Another thing is having even a simple node which maintains an updatable state and responds to network requests will be tough to pull off. I think we could do it, but the probably that something will go wrong will be super high and we may end crushing the demon on stage.

So, we need to see to which extent we can simplify the requirements of the demo. I think we can still showcase client-side proving, but it would probably need to be done on a laptop and probably we should avoid making it interactive.

We should totally do an interactive demo in the future, but for this, we probably want to have the basic node running for at least several weeks so that we have the time to work out the kinks.

[Dominik1999]

Interesting. Thanks for the comments.

I just quickly tested, and $2^{15}$ works with my phone (iPhone 13) in 5s. This is the Game of Life program with 14 generations and a trace_len of 32678. But to create a transaction, do we need to verify Falcon signatures? I may have to see transaction proofs end-to-end to get a better understanding.

What I understand is we need to see how many cycles it costs for a proof of the simplest transaction possible. If this will not be possible on a standard mobile in three weeks, we should change the talk.

[bobbinth]

I just quickly tested, and $2^{15}$ works with my phone (iPhone 13) in 5s.

Great benchmark! For comparison, $2^{15}$ cycles takes about 0.3s on an M1 Pro.

One thing to keep in mind is that these proofs are generated using BLAKE3 hash function - so, they are not suitable for recursion. If I were to generate the same proof using RPO hash function, it would take 3.4s on an M1 Pro without GPU acceleration, and 1.6s with GPU acceleration enabled.

But to create a transaction, do we need to verify Falcon signatures?

Yes, if we want to send funds out of the account, we need to prove locally that we know a Falcon signature which authorizes the transaction.

What I understand is we need to see how many cycles it costs for a proof of the simplest transaction possible. If this will not be possible on a standard mobile in three weeks, we should change the talk.

The simplest transaction possible would be to send funds out of the account. For a real transaction that does this, we'd need to use Falcon (or some other) signature and RPO hash function, and this likely means proving times of 30 - 60 seconds on mobiles phones.

Unless we can relax some of these constraints, we should change the talk.

[frisitano]

Yes, if we want to send funds out of the account, we need to prove locally that we know a Falcon signature which authorizes the transaction.

In the interim if Falcon signature is not available, we could consider using a different authorisation mechanic. Something simple would be to say that I know a pre-image that hashes to a digest stored in an account storage slot. The pre-image would be provided via non-determinism and the assertion that it hashes to the digest would be done as part of the transaction authorisation hook. This isn't a production ready solution but may be fine for demo purposes.

[frisitano]

Current Transaction Kernel status:

• Can consume notes including authentication using merkle path
• Can create notes with a single asset and arbitrary recipient
• Can modify account storage
• Cannot add or remove assets from an account vault
• Cannot assert invariant of asset creation / destruction across transaction execution
• Cannot mint or burn assets using faucet

Proposal:

• Consume a note with two assets in it's vault
• As part of the note script we iterate over the two assets and send each asset onto a new recipient using a new note.
• Transaction has a single note input and two note outputs with different recipients. Account state does not change.

[Dominik1999]

Thanks a lot. I don't quite understand yet what the delta is to a fully functioning transaction.

1. we cannot change account states yet (adding/removing assets)
2. we cannot sign nor verify signatures yet (authorizing a transaction)

Both seem quite fundamental to transactions. Is this correctly understood? If so, a couple of questions:

• can we verify such a transaction that you propose?
• can we add 1. or 2. or both until Friday this week? (it can be hacky without Bobbin's review)

[frisitano]

Thanks a lot. I don't quite understand yet what the delta is to a fully functioning transaction.

1. we cannot change account states yet (adding/removing assets)
2. we cannot sign nor verify signatures yet (authorizing a transaction)

Both seem quite fundamental to transactions. Is this correctly understood? If so, a couple of questions:

• can we verify such a transaction that you propose?

Yes we have the means of proving the transaction that I propose.

• can we add 1. or 2. or both until Friday this week? (it can be hacky without Bobbin's review)

For 1) this requires the implementation of the AccountVault in masm. This is not possible at the current point in time as the TieredSmt masm implementation is not complete. We could replace the TieredSmt with a SimpleSmt but this would require refactoring the rust side. We would then need to implement the AccountVault masm logic. This is a significant undertaking in itself and my concern would be that it would take some time and then we wouldn't have the time to wire up the front end.

For 2) I would defer to @Al-Kindi-0 but from our conversations I understand that Falcon verification takes around 100k cycles - this would not be practical for a mobile phone.

[Dominik1999]

Ok, understood. So we wont have 1..

But could we use the Falcon verification on a computer to show a tx proof live on stage? So is the Falcon verification implemented in the tx kernel or tx procedure?

[frisitano]

Ok, understood. So we wont have 1..

But could we use the Falcon verification on a computer to show a tx proof live on stage? So is the Falcon verification implemented in the tx kernel or tx procedure?

The Falcon signature verification is implemented in the standard library - https://github.com/0xPolygonMiden/miden-vm/blob/main/stdlib/asm/crypto/dsa/falcon.masm#L206-L278. However, it is not a hard requirement. The purpose of the signature is to provide authorisation to perform some action inside the VM (e.g. spend some assets). However, I have proposed an alternative of using a password like authorisation above. This certainly ins't production ready but maybe a viable alternative for now. I'm also not sure if we have the Falcon signing algorithm implemented in rust so I'm not sure on how we would go about creating signatures (maybe we can generate static signatures using a different implementation and persist them for the demo) - @Al-Kindi-0 should be able to share some light on this.

The other alternative is to ignore authorisation completely and just demonstrate consuming a note and producing two new notes.

[Al-Kindi-0]

The other alternative is to ignore authorisation completely and just demonstrate consuming a note and producing two new notes.

I am leaning toward this. I think that the most "exciting" thing would be to show the client side capabilities that will be fundamental to our rollup design. Authorization is "just" a hidden tool that enables that and so we can opt for either something very simple (like @frisitano has proposed) or drop it altogether and mention during the demo that "... this assumes that the sender has authorized this action using a DSA. Miden uses Falcon is a good candidate as it is plausibly post-quantum secure and zk-VM friendly..." or something along these lines. These are my 2 cents :smile:

[Dominik1999]

Got it. If we skip the authorization part, how many cycles do we have then in @frisitano's example?

And do we use Blake3 or RPO for the whole transaction?

I am asking because I wonder how close we are to a real transaction.

[frisitano]

Got it. If we skip the authorization part, how many cycles do we have then in @frisitano's example?

And do we use Blake3 or RPO for the whole transaction?

I am asking because I wonder how close we are to a real transaction.

We have 2554 cycles. This doesn't have authorisation implemented. However, using knowledge of a 256 bit pre-image as an authorisation mechanic would only add a few cycles. I think this authorisation mechanic illustrates how client side proving can open up new possibilities.

[frisitano]

flagging blocker: https://github.com/0xPolygonMiden/miden-vm/issues/1004

[frisitano]

flagging verification bug: https://github.com/0xPolygonMiden/miden-vm/issues/1007

[frisitano]

flagging verification bug: 0xPolygonMiden/miden-vm#1007

verification bug addressed - was a problem related to constructing the StackOutputs.

[bobbinth]

flagging blocker: 0xPolygonMiden/miden-vm#1004

Should be addressed by https://github.com/0xPolygonMiden/miden-vm/pull/1008.