.... Programmable Zcash? (TOTALLY NOT CLiCKBAIT)

Fr though, not clickbait. CC @hanh, @ValarDragon, @ebfull, @aquietinvestor , @nuttycom , @str4d

So, for a long time, and I mean a LONG time, everyone has basically went “shielded programmability? SHIT EXPENSIVE, ABORT MISSION!”

Well, until about 4 days ago when I was taking a shower. I was like “wait fool, Halo2, they use like, fixed constraints right? and fool, their vanishing argument is algebraic and additive over a polynomial yes? then holy shit, you can technically just take the vanishing argument and general layout of ANY given circuit B without revealing circuit B or its inputs!”

So, I present to you…

DELTA EXECUTION ARGUMENTS (the DEA, this is not a joke, and I did NOT smoke sinsemilla while writing this)

A DEA (or. a “delta”) package is a succinct, verifiable proof of execution of any arbitrary computation between two circuits where one circuit is a functional superset of the other circuit, where the produced overall proof is valid against both A and B (B being superset of A).

How does this apply to Zcash? Well, technically, the Orchard/Ironwood circuit is, well, a circuit. If you consider the Ironwood circuit as a circuit A, and then fix its layout and instead fill its 200 “padding” rows with actual computation, the resulting circuit B is actually a functional superset of A

This means that our primitive, DEA, can be used to provide a succinct proof of execution of SOME computation over a superset circuit of Ironwood, basically, proving that a program ran correctly and it satisfies all Ironwood constraints AND a given private program’s constraints.

So, I… got to work.

I am now very proud to present the numbers…

THE PROOF PACKAGE

Question Answer
What is the size of the additional proof data per Action? In the current version, 1152 bytes
Of which the delta argument is? 768 bytes flat
Of which the gate proof (that the executed program was really the committed program 64 bytes
How long does it take to verify? Just 4.7% more time than a standard Action proof
How long to verify a batch of 16? Just 11% more time than 16 normal Action proofs
How long to prove one? In our tests with the stock MockProver, ~21% to 26% slower, but Zakura should change this

And get this.

EVERY SINGLE PROGRAM THAT COULD POSSIBLY BE WRITTEN IS INDISTINGUISHABLE. Their proof packages and delta arguments are EXACTLY THE SAME SIZE. OH MY GOD.

But is this even practical for anything?

Let’s see… what have I tested so far?

  • Spend limits
  • Fee cap
  • Invoice (payment to commitment)
  • Escrow
  • Denylist
  • Travel rule

BUT IT GETS BETTER

I also realised that technically, the psi field is just there for the taking. Because psi_old is available, and psi_new can be enforced (the proof can fail if its not set correctly), the UTXO can PROPAGATE STATE FORWARD.

This means it can communicate and retain state between spends. What does this enable you ask?

Programs like THESE

# Vault: capped withdrawals, no clock needed                     ~56 rows
tag, count, withdrawn = unpack(psi_old)                          # 25
if tag == VAULT:                                                 # 1
    amount = v_old - v_new                  # what leaves the vault in this Action
    assert amount <= PER_WITHDRAWAL                              # 9
    assert withdrawn + amount <= LIFETIME_CAP                    # 9
    assert count < MAX_WITHDRAWALS                               # 9
    assert (g_d_new, pk_d_new) == (g_d_old, pk_d_old)            # 2: change stays in the vault
    assert psi_new == pack(VAULT, count + 1, withdrawn + amount) # 1

Vaults that can “peel off” money upto a withdrawal limit per spend!

And if we can lobby to add nLockTime to Orchard/Ironwood proofs, then actual time-based locking!

Yes, I have implemented this and it works… beautifully wipes tear

DISCLAMER: This post is made by me (the operator of this account), not by Strahn Cryptography, and so don’t take it as a formal announcement. It just is.

Would love a discussion in the comments about this. Ask for LITERALLY anything about this. Even name any program and I’ll see if it can be implemented.

Since this relies on the “padding” rows of the circuit, the functional limit is 210 rows. Programs work like a 1950 drum memory, so I guess we have a lot of optimisation to do.

Code isn’t pretty rn, it’s basically an assembler, but some examples:

Example programs

/// Invoice settlement: pays amount to merchant, and B’s private inputs (invoice id, salt)
/// hash to invoice_hash in domain.
pub fn invoice(merchant: Fp, amount: u64, domain: &str, invoice_hash: Fp) → Result<Program2, AsmError> {
let mut a = Asm::new();
a.assert_zero(port(Port::PkdNewX) - Expr::constant(merchant))
.assert_zero(port(Port::VNew) - c(amount));
a.input(0); // invoice id
a.input(1); // salt
a.set(2, c(1u64)).hash(domain, Some(invoice_hash));
a.finish()
}

/// Escrow release: pay the escrow agent, or reveal the secret that hashes to release_hash.
/// The slot checks (hash - release\\\_hash) \\cdot (recipient - agent) = 0.
pub fn escrow(agent: Fp, domain: &str, release_hash: Fp) → Result<Program2, AsmError> {
let mut a = Asm::new();
a.set(2, port(Port::PkdNewX) - Expr::constant(agent));
a.input(0); // the secret
a.set(1, c(0u64)).hash(domain, Some(release_hash));
a.finish()
}

and the largest one of the lot

/// Vault: a note whose ψ carries a vault state may only be spent by sending at most
/// `per_withdrawal` out of it, at most `lifetime_cap` in total and at most `max_withdrawals`
/// times; the change must stay at the vault's address with the updated state. Notes without
/// the vault state are unrestricted.
pub fn vault(per_withdrawal: u64, lifetime_cap: u64, max_withdrawals: u64) -> Result<Program2, AsmError> {
    let two70 = pow2(70);
    let mut a = Asm::new();
    // Canonical unpacking: 26 words, then the top word below 16, so ψ < 2^254 < p and the
    // decomposition is unique. Taps: R0 = ψ, R1 = ψ >> 70, R2 = ψ >> 140, R3 = ψ >> 250.
    a.range(port(Port::PsiOld), 26, &[(0, 0), (7, 1), (14, 2), (25, 3)])
        .range(r(3) * Fp::from(64), 1, &[])
        .set(3, r(0) - r(1) * two70) // R3 = withdrawn
        .set(0, r(2) - c(VAULT_TAG)) // R0 = (ψ >> 140) − tag: zero only for vault notes
        .set(2, r(1) - r(2) * two70) // R2 = count
        .iszero(1); // R1 = [vault note]
    // Each rule is multiplied by the vault bit, so it's vacuous for other notes.
    // amount = v_old − v_new ≤ per_withdrawal
    a.set(0, c(per_withdrawal) - port(Port::VOld))
        .set(0, r(0) + port(Port::VNew))
        .mul(0)
        .assert_nonneg(r(0));
    // withdrawn + amount ≤ lifetime_cap
    a.set(0, c(lifetime_cap) - r(3) - port(Port::VOld))
        .set(0, r(0) + port(Port::VNew))
        .mul(0)
        .assert_nonneg(r(0));
    // count < max_withdrawals
    a.set(0, c(max_withdrawals - 1) - r(2)).mul(0).assert_nonneg(r(0));
    // The change stays at the vault's address.
    a.set(0, port(Port::PkdOldX))
        .set(0, port(Port::PkdNewX) - r(0))
        .mul(0)
        .assert_zero(r(0));
    a.set(0, port(Port::GdOldX))
        .set(0, port(Port::GdNewX) - r(0))
        .mul(0)
        .assert_zero(r(0));
    // ψ_new = pack(tag, count + 1, withdrawn + v_old − v_new)
    a.set(
        0,
        Expr::constant(Fp::from(VAULT_TAG) * pow2(140) + two70) + r(2) * two70 + r(3) + port(Port::VOld),
    )
    .set(0, r(0) - port(Port::VNew))
    .set(0, port(Port::PsiNew) - r(0))
    .mul(0)
    .assert_zero(r(0));
    a.finish()
}

CC @zeckzodel, @dismad for their valuable takes

5 Likes

I will try my best to drop a civilised, proper announcement soon, as well as all the code I used to test stuff.

2 Likes

Feel like I have to put this out there.

No, this is not an approved list of programs.

You can commit to ANY arbitrary program, execute it off-chain, then prove that you executed a program you yourself defined without the node or any observer ever learning what condition or why.

An invalid execution simply generates an invalid proof, so the UTXO becomes unspendable.

It is impossible to tell what conditions a UTXO was locked to unless you were given the lock, similar to Taproot.

1 Like

Interesting. A question from the escrow side, since you list it.

In a 2-of-3 FROST escrow (buyer, seller, arbiter), the residual risk is collusion: any two signers can send the note anywhere. What we’d want from a program is narrower than your hash-release example: the note may only be spent to one of two committed recipients, the buyer’s refund address or the seller’s payout address, for the full amount minus a fee cap. Then even arbiter plus one party can only pick a side, not take the money.

Could that be expressed with two committed pk_d values in the program and an OR on the output? And is the propagated state enough to also enforce “refund only after height H”, or does that still need a separate timelock change?

Which consensus change would DEA itself need to go live?

1 Like

That is 100% doable. In fact, it would take just 25-30 rows of the ~200 allowed rows.

But you’d have to specify the full address, not just pk_d.

The program would essentially be much like:

s = private input                 # 0 = refund to the buyer, 1 = payout to the seller
assert s·(s − 1) = 0
assert g_d_new  = G_buyer + s·(G_seller − G_buyer)    # full points, x and y
assert pk_d_new = P_buyer + s·(P_seller − P_buyer)
assert v_new + FEE_CAP ≥ v_old

That’s it.

That would require nLockTime to be added to the Ironwood circuit as a public or private input, so yeah, it would require a change. But once that’s added, programs get a reliable sense of what the minimum passed time is.

A pretty big one, essentially an NU scale upgrade. The math itself works, it is fine, but we need time to draft a ZIP, do Lean proofs, get ZCG grants to pay developers, yada yada

But all that only starts rolling with community support, because the default posture is always “this isn’t fit for Zcash”, especially given current governance issues. So, show support, and react on the original post!

3 Likes

If this passes Lean based on nothing more than cryptographic hardness assumptions, then it’s a heroic discovery. Holding my breath, meanwhile.

And if so, did you just enable “zunker” mode (among zillions of other small functions)? What I mean is:

  1. I’ve sent Z ZEC to address A.

  2. Under Vitalik’s bunker mode, I just leave it there because, with no outbound transactions, there’s no elliptic curve public key for AI and QC to crack. There’s only a hash, which is undoubtedly a higher bar.

  3. But this still isn’t good enough because I have weak security practices. So I use your method to say “Only allow this wallet to transfer to addresses B, C, and D.”

  4. I make paper wallets for B, C, and D. I bury one each under the hippo, giraffe, and camel paddocks at the zoo. You know, just in case the camel poops on one of them, I have the others.

  5. I show up at the coffee shop. I reach for the $10 bill in my pocket to pay the cashier, but accidentally pull out the paper wallet for address A, which I keep handy in case I ever want to move my funds. (Keeping it in my pocket exposes me to wrench attackers but that’s fine because I’ve always wanted to interview one for my YouTube channel.)

  6. The reflection of the paper wallet on the metal milk pitcher appears in one video frame of the coffee shop’s hacked security camera.

  7. A second later, at some hacker’s data center, the reflection is flattened, deblurred, recognized into characters, then partially reconstructed using the known list of valid words.

  8. Unknown words are few and discovered computationally on GPUs.

  9. After a minute, some AI agent has my seed phrase A and attempts a drain.

  10. It fails because of step 3.

  11. Even B, C, and D could be hacked, so long as they, in turn, are also in zunker mode (or they aren’t but A is still secret).

If you can provide even 2 exit addresses… it’s zunkers all the way down!

You could even combine them with your timelocks to force downstream subdivision in case seed phrase A gets lost, with transaction fees prepaid in the initial timelock setup. And doing all this with u-addresses would be a game changer.

Am I missing something?

You’re not! That is EXACTLY what this allows!

In step 3, you generate a program circuit that simply evaluates an OR gate over 3 pairs of 2 AND gates each to check if the destination address is one of three allowed ones.

To spend the UTXO from that point on:

  • You need the original program code, just like Taproot. This is ideally put in the memo so you don’t lose it.
  • You need the ivk of the account which received the UTXO (this one is more complex, we’re still building, so this requirement may change)
  • You need the actual addresses of B, C, D.

Then when you start computing the proof, the program checks the pk_d and g_d of the destination note. If they don’t pass any OR gate (match no address in the allowed set), the proof fails. Because it’s a combined proof for A and B, the standard Ironwood proof also becomes invalid. Any transaction which doesn’t meet your criteria (sending all value to B, C or D) cannot possibly generate a valid proof!

In fact, you can do this with upto 200~ish addresses!

Honestly, I will have to look into that, I’m pretty sleep deprived right now haha

But no, you aren’t missing anything

In fact, if the checksig part (the part where the Ironwood circuit validates access to the spending key) can be dropped and moved to B just like in Bitcoin (where redeem scripts can choose to just drop the checksig), one can replace the standard spending key requirement with any arbitrary predicate lol

From knowing an obscure constant to knowing a preimage of a given hash, it’s creativity galore!

Here’s how I now think zunker mode would work, leveraging what you said above. It might make a good early application of your novel Zuring machine. (This probably needs its own thread because your scope here is much larger, but first please let me know if something below is inefficient or stupid.)

  • Your wallet A does some prep work to suck up your entire history into a single UTXO (the “bag” UTXO), except for a single “entry fee” UTXO left for zunker entry. If it’s not economical to transfer dust amounts, or you exceed the input UTXO count limit, then the wallet warns accordingly.

  • You specify addresses (B, C, D) (or however many, maybe variable).

  • An orderly exit (meaning one signed by A so compromised exits can be avoided) can only send the entire bag UTXO. It will fail to any other address. The exit fee should be injected just prior to the exit itself, depending upon the fee computation in force at the time. (Even under constant consensus ID, the fee might be dynamic and should therefore be left to exit time.)

  • The wallet does some sanity checks on (B, C, D), such as making sure that they’re valid, A doesn’t own any of them, there are no repeats, and none has ever sent out anything (which would violate Vitalik’s bunker).

  • All 4 wallets could actually be multisigs. That’s independent of any of this.

  • It’s possible that the seed for A will get lost. In that case, the backup is a disorderly exit (meaning signed by anyone, no checksig) of the funds in some subdivision (Zb, Zc, Zd) to (B, C, D). As before, exit fees are left to be injected at the last minute. The wallet ensures that (Zb, Zc, Zd) equals the bag UTXO. (Unfortunately they can’t be fractions because there’s no way to implicitly include UTXOs that haven’t yet been received so unexpected receipts become spendable by A to anywhere.)

  • You specify some block expiry E upon which orderly exits become impossible and disorderly exits become possible. The wallet fails if it’s before, say, a day from now, and warns if it’s maybe over a year away.

Some will say that you can just do all this with MPC or multisig equally well. Maybe that’s true but then you have to sit there for the entire hodling period, all the while just hoping that your offline quorum address computation was correct, as you can’t violate Vitalik’s bunker in order to prove control. With zunker mode, you just need to compute one exit correctly, using a diversity of untrusted monosig wallet apps on offline devices destined for wiping.

2 Likes

“Zuring machine” :sob:

But yeah, your design would actually work! PROVIDED expiryHeight is also added as an input to the circuit ofc

I tried writing it as pseudocode (this has no expiryHeight rn sorry)

program ZUNKER   // constants: AKZ = x(ak_Z), F (buffer per note), h_A, bunkers (Gx[j], Px[j]), j < k
  t := [x(ak) == AKZ]                         // every note Z holds
  assert t·(F − (v_old − v_new)) ≥ 0          // at most F leaves the note: fees, or anything else
  s := private_input(); assert s ∈ {0..k−1}  // bunker being paid
  assert t·(x(pk_d_new) − select(s, Px)) == 0
  assert t·(x(g_d_new)  − select(s, Gx)) == 0
  secret := private_input()
  hash_slot: (SinsemillaHash(secret ‖ 0) − h_A) · t·(s − ψ_old) == 0

Looks very simple, and does basically everything you ask for lol

You set a maximum fee buffer per Zunker (maximum amount you can sweep out of a Zunker to pay for fees of the redemption transaction). Or if the buffer is zero, fees have to be injected by someone else to pay for the transaction.

I got Claude to rewrite it in english

PROGRAM ZUNKER

  FIXED AT SETUP (hidden inside the program):
    Z_ACCOUNT   = x-coordinate of Z's ak
    FEE_BUFFER  = the most value that may leave one note
    A_HASH      = hash of A's secret
    BUNKERS     = list of k addresses, each a pair (g_d, pk_d)

  RUN ON EVERY ACTION IN THE TRANSACTION:

    IS_ZUNKER_NOTE := (x-coordinate of the spender's ak == Z_ACCOUNT)
    IF NOT IS_ZUNKER_NOTE:
      ACCEPT                            -- fee, bounty and unrelated actions pass

    REQUIRE old note's value − new note's value ≤ FEE_BUFFER
                -- that much may go to fees or bounty; the rest stays in the note

    CHOSEN := private input from the prover
    REQUIRE CHOSEN is one of 0, 1, …, k−1      -- which bunker is being paid

    REQUIRE x-coordinate of new note's pk_d == x-coordinate of BUNKERS[CHOSEN].pk_d
    REQUIRE x-coordinate of new note's g_d  == x-coordinate of BUNKERS[CHOSEN].g_d

    IF CHOSEN == old note's     -- the bunker this note was earmarked for at entry
      ACCEPT                               -- disorderly exit: anyone may do this
    ELSE:
      SECRET := private input from the prover
      REQUIRE Sinsemilla hash of (SECRET, 0) == A_HASH
      ACCEPT                              -- orderly exit: only A, to any bunker
REJECT
FINISH

Does this make sense for your version of Zunker?

That would require removing CheckSig, BUT it can be done without doing that too! Just send funds to a new seed, and make the seed public. The funds cannot be spent anyways unless they meet the condition.

Wait, strike that. A can’t be made public ofc.

I had Claude implement it in rough Assembly. Your entire Zunker would take just 74-ish rows out of available 210~ish, and even then about 27 of the rows are just waiting for the memory “drum” to cycle. We will have to reach back to the 1950s and pull out algorithms to optimise that with a whole ass scheduler later.

@strahncryptography @zeckzodel ZUNKER reads the earmarked bunker from psi_old, and the vault in post 1 keeps its counters in psi. That’s a problem for wallets as they work today.

psi is derived from rseed (note.rs), and the note plaintext carries rseed, not psi. A stock wallet rebuilds the note from rseed when it decrypts (note_encryption.rs), so a note with state in psi gets a different commitment and the wallet drops it. One restored from Z’s seed wouldn’t find the zunker notes.

How would a wallet find them: a new note plaintext that carries psi, or psi recomputed from the previous state?

The selection of psi for state is not serious and is merely an example of a circuit private input being used as a 256-bit bitfield to retain and propagate state. If this is seriously implemented, of course a new state bitfield will be used.

2 Likes

Thanks, @strahncryptography, that’s a clean answer. So escrow becomes “pick a side” instead of “trust two signers”: the arbiter plus one party can only decide refund or payout, never redirect the funds. That’s the one risk left in our 2-of-3 FROST escrow (testnet, predgeAI/zcash-escrow), so we’d be a real early user.

Two things we can contribute while the ZIP is being written:

  • an escrow program spec (two full committed addresses, fee cap, and the height-H refund once nLockTime is a circuit input), with accepted and refused transactions as test vectors;
  • a write-up of how wallets and co-signers would need to handle it, building on the frost-zec tamper cases.

Happy to start on the first one when your code is up. Reacted on the original post too.

@predge-ai for the escrow program spec you offered, one case worth covering from the start: “never redirect” holds if the program is fixed when the note is created. Any two of the three already meet the 2-of-3 threshold, so if the program could be chosen at spend time, the arbiter and one party could prove under a different one. Signing doesn’t pin it either: in ZIP 244, Orchard proofs sit in the auth digest, not the sighash. If Ironwood keeps that split and the program travels only with the proof, the FROST signature stays valid whichever program the proof is built for.

Happy to help with the co-signer side: what each signer checks before its share leaves, and the refused cases for that part. The program’s own refused cases would sit with the circuit’s vectors.

@strahncryptography with the new state field you mentioned, where is the program committed for a note that a third party pays into the escrow: in the note, the address, or somewhere else?

Really interesting work. One question on the privacy side, about every program being indistinguishable.

Within the set of programmed Actions that holds, since every delta package is the same size. But the package itself (1152 bytes per Action) still marks an Action as programmed when it sits next to a plain Ironwood Action. If only some Actions carry it, programmed notes form their own smaller anonymity set, and an observer learns “this note has a spend condition” even without learning which one.

Is the plan for every Action to carry a delta package, with an empty program for ordinary spends, the same way Orchard pads bundles with dummy actions? That keeps one uniform Action format, but it puts the 4.7% verification cost and the extra bytes on every Action, so it would be good to see the numbers for that case too.

A smaller wallet-side point: since a note can only move when a valid witness exists for its program, a wallet should check before funding that every exit path can actually be proven (for the vault, a withdrawal within the caps; for escrow, both the refund and the payout). Otherwise a program with a mistake in it locks the funds for good, and nobody finds out until the first spend fails. A dry-run proof of each exit path at setup would catch that.

1 Like

That has nothing to do with the state. Every created Action will commit to a program via a 32 byte (or 64 byte, we’re not sure) commitment that nodes will store. This allows the node to execute a gate check that an executed program really was a previously committed program, identical to Taproot’s MAST (although with just one available script at present unless we add a hash tree, and WILDLY different mechanism)

Ideally, the payer uses the memo to write a program description and the receiver uses their IVK to reconstruct the program so they can execute it.

JUST LIKE Taproot, if the note who paid it in didn’t use scripting (just like if you don’t use P2TR in Taproot), its a standard, spendable-by-anyone note. Your mistake.

1 Like