AZTEC: How the Ceremony Works (Advanced Version)

August 30, 2019
4
MIN READ
Blog
>
>
>
AZTEC: How the Ceremony Works (Advanced Version)
|

– Advanced Version | Switch to Basic Version

Approach

We’ll first explain how AZTEC Notes get validated — in other words, how our range proof works.

That should help explain why we need a ceremony — in particular, why we require a register of points known as the AZTEC Codex.

References

AZTEC White Paper

{{blog_divider}}

Motivation

AZTEC’s Core Transaction is a confidential UTXO — given an input note of size k₁ we wish to spend money by generating output notes size k₂ and k₃ — for example, k₂ might be the amount you’re sending a counterparty, and k₃ may be the spare change you want to keep.

  1. k₁ = k₂ + k₃ —encryption via sigma protocols allows this to be easily checked — details in our White Paper
  2. k₂ and k₃ are both within a fixed range, and therefore the wrap-around attack (e.g. 10 = 11 + -1) is not available to the attacker

To achieve (2), the range proof, AZTEC instead deploys a proof of set membership — i.e. that the encrypted forms of k₂ and k₃ sit inside a proscribed set 1, 2, 3, …, Max.

{{blog_divider}}

How to Prove (2) — the Range Proof

AZTEC’s range proof extends a set membership technique of Camenish et al, using Boneh-Boyen signatures.

Suppose, somehow, there exists a register of encrypted numbers k, of the following form:

The AZTEC Codex, built on generator point h

Note that to the observer these are just points — they can’t explicitly ‘see’ y. So it’s nice to rewrite these as:

The Codex again, but neatening up the notation

Suppose further that another generator g₂ is raised to the power of y, and that the result of this has been published somewhere for all to see:

The AZTEC Reference Point

Well, it turns out that there’s a clever construction allowing a prover / spender to ‘wrap’ one of these numbers (we call this a ‘note’), and prove to a third party that either he / she knows the number y, or else that the note was formed from this register — in other words, that the number j is in the range.

This construction requires a fresh random number v (the viewing key) for each note, and is formed as follows:

An AZTEC Commitment — creating a note of value k, and viewing key v — please note that in the AZTEC White Paper this is actually denoted as the variable a

Note that this can be formed without knowledge of y. But magically, we have constructed two points with a special relationship — the right-hand argument can be rewritten as follows:

Rewriting the right-hand argument of the AZTEC Commitment — and out drops y

So, we’ve got a pair of points related by y.

Now, recall that an elliptic curve pairing allows ‘ratios’ of exponents to be compared — well, let’s haul in that Reference Point, and check:

Check that the ratio bedded into the AZTEC Note really is y

If this is true, what can we deduce?

Well, either:

  1. The spender had access to y, or
  2. The spender must have used one of the points from the AZTEC shelf (codex) — otherwise, generating a ‘ratio’ of y between these points would have been impossible

We need to stop (1) being an option.

That’s where the AZTEC Ceremony comes in — to avoid y ever being explicitly created.

{{blog_divider}}

The Mathematics of the Ceremony

We know what we need to do — we need to build that Codex of points, without y ever being explicitly constructed.

As a reminder, we need to construct Boneh-Boyen signatures for each k as follows:

The k’th Codex Point

Here’s the first observation — those Boneh-Boyen signatures are just expressions in y. How could we construct this not knowing y? Well, we can certainly do it if we know the following ‘monomials’ in y:

The monomials in y, in the exponent of h

If we could construct these, then the task of building that Codex is pretty simple — define two polynomials (we’ll be evaluating both of these at y):

Now notice that we can divide these to get:

In other words, we can find the k’th point of the Codex with the following computation:

And even better, we can do it without ever knowing y.

How?

Well, we just need to know Mon(y) (i.e. the monomials evaluated as elliptic curve points) and then compute all those coefficients — expensive and painful, yes.

But we only need to go through this once.

{{blog_divider}}

A Rotation Trick

Dividing in elliptic curve world is pretty hard work.

So here’s a trick. Let’s actually do everything base g, and then define h as:

Shifting the base point

We’ve essentially rotated the whole curve around by a factor of Γ(y), to avoid a nasty division!

{{blog_divider}}

Those Monomials — How Did You Make Them?

Fortunately, that’s the simplest bit of all — we have a relay.

Participant 1 takes the generator point h (computed from g as already seen), and then generates some toxic information z₁. Finally, they form Transcript 1 as follows:

Next, Participant 2 receives these points and rolls in their toxic information to form:

Note that Participant 2 does this just by exponentiating Participant 1’s points — never knowing what number z₁ was used to form them.

If there are (say) 100 participants, then the number y is in fact:

But, unless every single participant colluded with its neighbours, this number will never be known .

And We’re Done

Now to reattach names to the maths:

  1. The Relay — The process of forming Mon(y) by producing the Transcripts one after the next
  2. Post Processing — The process of computing those coefficients, and working out the Codex of Boneh Boyen signatures

So now you know what’s going on under the hood.

Check Circle 1 Streamline Icon: https://streamlinehq.com
Oops! Something went wrong. Please retry
By subscribing you agree to with our Privacy Policy and provide consent to receive updates from Aztec.