Skip to main content

Technical Specifications

Let us take a deep dive into some of the concepts under the hood which enables the anonymous transfers

The Statements to be proven​

In the anonymous transaction, the Prover's work broadly boils down to proving the following in zero-knowledge.

  • The validity of the commitments
  • The Merkle membership proof
  • Amount Sum Equality
  • Range proofs to demonstrate that all input/output values lie in the range [0,264][0, 2^{64}]
  • The correctness of the computation of the nullifier

The TurboPlonk Snark instantiated with the KZG polynomial commitment scheme allows the Prover to prove all of these statements with a single constant-sized proof. The proof generation time for each statement and consequently, for the batched proof, is superlinear (O(n⋅log⁡(n)))(\mathbb{O}(n\cdot \log(n))) in the size of the circuit. The size of the corresponding arithmetic circuit coincides with the size of the largest of these circuits, which is the circuit corresponding to the Merkle membership proof.

The runtime of an anonymous transfer is dominated by the Plonk proof generation for these statements. The runtime of the Plonk proof generation, in turn, is dominated by the zero knowledge Merkle Membership proof. Thus, it is vital for the runtime of this ZK Merkle Membership proof to be efficient or equivalently, for the corresponding circuit to be as small as possible. This is equivalent to the circuit for the knowledge of the pre-image of the hash being small. It is for this reason that the hashing algorithm used for the ABAR Merkle tree is a Snark-friendly hashing algorithm such as Rescue, Poseidon or MiMc. While these hashing algorithms are much slower than SHA-256, the circuit size of the Merkle membership proof with SHA-256 would be millions of gates, which would make the Prover's runtime far too expensive.

Validity of Commitments​

The Prover (the sender in the transaction) needs to prove that the input and output commitments are well-formed. In other words, they need to demonstrate knowledge of the asset types and amounts that correspond to the commitments recorded on the ledger. The input commitments are commitments of the 3-tuple - input amount, input asset type and the input randomness used to form the commitment. Similarly, the output commitments are the commitments of the 3-tuple - output amount, output asset type, and the output randomness.

For each sender uiu_i:

  • com.i=Com(amount.in.i,asset.type;r.in.i){com.i} = {Com(amount.in.i}, {asset.type}; r.in.i)

  • com.new.i=Com(amount.in.i,asset.type;r.in.new.i){com.new.i} = {Com(amount.in.i, asset.type; r.in.new.i)}

For each receiver vjv_j:

  • com.out.j=Com(amount.out.j,asset.type;r.out.j){com.out.j} = {Com(amount.out.j, asset.type; r.out.j)}

The Merkle membership proof​

As described earlier, the ABAR commitments are stored using an append-only tree, which we call the ABAR commitment tree. This is a 33-ary Merkle tree built using the Rescue hashing algorithm, i.e. each non-leaf is the Rescue hash of the concatenation of its three children.

The leaves of this Merkle tree contain the Pedersen commitments to the ABARs. A Pedersen commitment is endowed with two fundamental properties. It is binding in the sense that the data cannot be changed without changing the commitment. It is also hiding in the sense that no adversary can retrieve the data from its commitment. More precisely, even if the adversary suspects that a certain datum corresponds to a certain commitment, he is incapable of determining this.

The Prover (the sender of an ABAR) proves in zero knowledge that he possesses an ABAR and a sequence of Rescue hashes that go from this ABAR commitment to the publicly visible root hash of the ABAR tree. The Rescue hashing algorithm is designed so that the resulting circuit is substantially smaller than a similar circuit with a more standard hashing algorithm such as SHA-256 would be.

Amount Sum Equality​

The sender in an anonymous transfer needs to prove in zero-knowledge that:

  • in the case of a non-FRA asset, the sum of input amounts equals the the sum of output amounts
  • in the case of a the FRA asset, the sum of input amounts equals the the sum of output amounts plus the transaction fees.

This is necessary to ensure that no party is able to spend more than it possesses.

Range Proof​

The range proof ultimately proves that the amount that is being transferred from the sender to the receiver belongs to a certain non-negative range

The Nullifier Tree​

Unlike the ABAR tree, the nullifier tree does not need to support efficient zero-knowledge membership proofs. Hence, the hashing algorithm does not need to be Snark-friendly. The nullifier tree is built using the SHA-256 hashing algorithm.

On the other hand, the nullifier tree does need to support efficient non-membership proofs to demonstrate non-repetition, especially for Verifiers running light nodes. For this reason, the nullifier set is stored using a binary sparse Merkle tree. This allows for more efficient non-membership proofs.

Anatomy of the AXfrProof​

The batched zk-Snark (TurboPlonk) proof of all the statements to be proven, along with the merkle root, is made available as a part of the AXfrProof.

pub struct AXfrProof {
pub snark_proof: SnarkProof,
pub merkle_root: BLSScalar,
pub merkle_root_version: usize,
}

AXfrBody consists of the AXfrProof along with other important components of the anonymous transaction such as the inputs, output ABARs and the owner memo.

pub struct AXfrBody {
pub inputs: Vec<(Nullifier, AXfrPubKey)>,
pub outputs: Vec<AnonBlindAssetRecord>,
pub proof: AXfrProof,
pub owner_memos: Vec<OwnerMemo>,
}

This AXfrBody along with the signatures make up the AXfrNote, which is broadcasted to the network by the sender while doing the anonymous transfer.

pub struct AXfrNote {
pub body: AXfrBody,
pub signatures: Vec<AXfrSignature>,
}

BLS12-381 Curve​

PLONK hinges on elliptic curve pairings and hence, needs to be instantiated with a pairing-friendly elliptic curve. For 128128-bit security, the number field sieve attack necessitates a curve defined over a field of bit-size around 380380. A popular candidate for a pairing-friendly elliptic curve is the BLS12-381 curve, thus named because it is defined over a prime finite field Fℓ\mathbb{F}_{\ell} of bit-size 381381 and has embedding degree 1212 with respect to a 255255-bit prime pp that divides the number of points on the elliptic curve. The Plonk is instantiated with the optimal ate pairing on this curve. The FFTs on the Prover's end all occur in this field Fp\mathbb{F}_p, which is known as the BLS12-381 scalar field.

The key parameters for a BLS curve are set using a single parameter x that can be selected to give the curve nice properties for implementation.

Specific design goals for BLS12-381 are:

  • x has “low hamming weight”, meaning that it has very few bits set to 1. This is particularly important for the efficiency of the algorithm that calculates pairings (the Miller loop).

  • The field modulus ℓ\ell mentioned above is a prime and has 383 bits or fewer, which makes 64-bit or 32-bit arithmetic on it more efficient.

  • The order pp of the subgroups we use is a prime and has 255 bits or fewer, which is good for the same reason as above.

  • The security target is 128 bits.

  • We want to have a large power-of-22 root of unity in the field Fp\mathbb{F}_p. Equivalently, we want p−1p-1 (the size of the multiplicative group of the scalar field) to be divisible by a large power of 22. This property is key to being able to use the Fast Fourier transforms efficiently.

The value x=−0xd201000000010000x = -0xd201000000010000 (hexadecimal, note that it is negative) gives the largest ℓ\ell and the lowest Hamming weight meeting these criteria. With this x value we have,

ParameterEquationValue (hexadecimal)
Field modulusℓ\ell13(x−1)2(x4−x2+1)+x\frac{1}{3}(x−1)^2(x^4−x^2+1)+x0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
Subgroup sizepp(x4−x2+1)+x(x^4−x^2+1)+x0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001

The Common Reference String​

The runtime of an anonymous transaction is dominated by the generation of the Plonk proof. Thus, improving the throughput for anonymous transactions largely boils down to optimizing the Plonk proof generation time. The parameters for our Plonk are chosen so as to optimize performance while still allowing for a security level of 128-bits. The common reference string (CRS) of PLONK consists of a vector of points on the BLS12-381 elliptic curve and is linear in the size of the circuit. The CRS is universal, i.e. the same CRS can be used to prove all necessary statements. It is also updateable, i.e. a new user can update the CRS using his privately generated randomness without having to perform a multi-party computation with the participants in the existing CRS. Thus, the CRS can be updated periodically.

© Findora 2022
|
|