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