bkase

I work on the tooling layer for zkapps on Mina — Great questions!

I think in the future the overhead will improve significantly, and we can already see incremental improvements in some proof systems. For Kimchi (the proof system we’ve built for zkapps/Mina), we've instead focused on features — like infinite recursion. To really see the performance overhead reduce, we’ll need to push more of the compute into silicon (think opcodes designed for zk similar to the ones we have now to accelerate RSA). In the meantime, modern processors are fast enough that this overhead doesn’t hold back many sorts of applications.

On fixed inputs: Kimchi is “universal” in that it can recursively compose arbitrary circuits efficiently — including ones with different public and private inputs and including ones that haven’t been defined yet. This is what powers zkapps and zkapps’ ability to recursively compose circuits on itself (think application-specific rollups).

Randomness: Modern blockchains have mechanisms for trustlessly agreeing on securely generated random seeds. We can tap into that and use mechanisms like verifiable random functions (which Mina uses internally during consensus) to securely manage randomness (caveat: we haven’t built out the randomness APIs for zkapps yet so there may be some nuance here that we haven’t run into yet). If you want to learn more about how this works in Mina, read up on Ouroboros Samasika, Mina Protocol’s consensus mechanism.

Prevent replay attacks: Blockchains are designed for this :). Basically increment a nonce and feed the current nonce as one of the public inputs to the zkapp.

Remote attestation: This requires nuance to define properly as there are different solutions to different versions of this problem. I’ll outline a few here:

1. Consider the case where you trust the entity that attesting to something and they can upgrade their backend: the entity adds a snark friendly signature to their endpoint and you check the signature within the zkapp (remember since they run locally, you execution can just make async network requests)

2. Consider the case where you trust the entity but can’t convince them to change their API: here you can verify the contents of the response against the TLS signature that already exists in the modern web. Caveat: this is still a work in progress, we’re currently calling it zkOracles

3. Consider the case where you don’t trust the entity — in this case we’re talking about reading information from other zkapps or blockchains. Luckily, these all come with signatures in different shapes and sizes so the problem becomes efficiently verifying those signatures from within the zkapp. You can solve this in modern plonkish zk proof systems with custom gates. Caveat: this is also a work in progress for zkapps in Mina.

Unfortunately, I don't actually have access to NVidia hardware anymore -- but I would be happy to accept a PR from someone who can get this to run!

Which links specifically are broken?

One of the authors here: Happy to answer any questions. Keep in mind this was a school project from 2012 (Kayvon's 15-418 at CMU, a wonderful class), so it's been a while.

Oh good, I'm glad we did mention this!

One of the authors here:

Yes you are right, you should not replace grep for one off regexes due to the latency of the io operations. As far as I recall, memory throughput however is much higher on house than on CPUs (or at least this was true in 2012). Our intended use cases for this sort of a grep were cases where you are finding many needles in enormous haystacks such as: Looking for malicious machine code in executables that you download off of the internet (virus scanning), or searching for certain genetic sequences in DNA code. I believe we discussed this in our final presentation, but perhaps we left it out of the written report.

Yes we probably should have included the numbers to show why you wouldn't want to use this instead of grep for simple tasks. I am sorry we missed it.

I enjoyed the post, but there's something that bothers me about using the name CRDT.

A CRDT is just what mathematicians (and functional programmers) call a Semilattice[1], right? In general, I find it frustrating when people make up new names for existing mathematical concepts because it deprives others from learning and seeing the big picture. Does this resonate with anyone here?

Another interesting problem slightly more interesting than a quine is writing an auto-cannibal machine (this was a homework assignment in my semester of 15-251 at CMU):

Write a function `ACM : (String -> a) -> a` aka a function that takes a string consumer as input (such as flip_upper_and_lower_cases: String -> String, or word-count String -> Int) and outputs the result of applying this transform to it's own source code.

For example if the contents of the ACM file were: `ACM(f) = print f("foo")` (note that this is clearly not a correct answer in any language)

`ACM(flip_upper_and_lower_cases)` invoked from another file should yield: 'acm(F) = PRINT F("FOO")'

(please don't post a solution publicly just in case they're still using this as homework)

I found your post very compelling. I have tried messing around with the APL derivatives (J and K and Q), but never created anything substantial. I didn't know you could view the AST like that, and it did really help in your explanation. I'm definitely going to check out an APL again! Thank you for the great post!

I've been using scm_breeze for a couple years, and it really makes me more productive with Git.

My favorite feature is that after a `gs` all the files listed are bound to sh variables $e1, $e2, etc.