Deep into AVM (Aleo Virtual Machine)
Recently, I had some free time and took a look at Aleo’s AVM design. The design of the privacy-centric virtual machine requires a comprehensive understanding of zero-knowledge proof technology, making it a great opportunity to learn about zero-knowledge proof techniques and design. The implementation of AVM can be found in the snarkVM repository on GitHub:
https://github.com/AleoHQ/snarkVM.git
The AVM-related logic discussed in this document corresponds to the latest commit on GitHub:
sqlCopy code
commit b862d4b680358aef9571df4bb6126e23618ab513 (HEAD -> testnet3)
Merge: 5da6fb5d4 23d007336
Author: Howard Wu <9260812+howardwu@users.noreply.github.com>
Date: Fri May 5 14:56:21 2023 -0700
Merge pull request #1509 from AleoHQ/dependabot/cargo/serde-1.0.162
Bump serde from 1.0.160 to 1.0.162Global State
Aleo is implementing a privacy computing platform. To protect privacy, the original transaction information should not be exposed in the global state. The global state is represented by the Merkle root of the block header’s Merkle tree.
Transition is a new term. It refers to the changes in certain states within a transaction. Transaction data is stored in blocks after being “encrypted.” In simple terms, unlike the global state in general blockchains, the original transaction data is not directly included in the global state.
Account Information
An account includes three types of keys: private_key, view_key, and address.
Account information is defined in account/src/lib.rs:
pub struct Account<N: Network> {
/// The account private key.
private_key: PrivateKey<N>,
/// The account view key.
view_key: ViewKey<N>,
/// The account address.
address: Address<N>,
}The three keys are generated as follows:
The most critical component in the private key is the seed. It can be said that all keys can be derived from the seed. The pk_sig and pr_sig are also public information.
Signature Algorithm
The signature algorithm is defined in console/account/src/signature/sign.rs:
/// Returns a signature `(challenge, response, compute_key)` for a given message and RNG, where:
/// challenge := HashToScalar(nonce * G, pk_sig, pr_sig, address, message)
/// response := nonce - challenge * private_key.sk_sig()
pub fn sign<R: Rng + CryptoRng>(private_key: &PrivateKey<N>, message: &[Field<N>], rng: &mut R) -> Result<Self> {The message is the original data that needs to be signed, and the nonce is randomly selected.
A signature consists of a challenge, a response, and a compute key. When verifying the signature, the g_r can be recalculated using the challenge/response and pk_sig. With the given compute key/address/message, it is possible to determine whether the challenge is correct, thus confirming knowledge of sk_sig.
What is Record/Transition?
A Record represents certain states of a program in the global state. For example, the balance of an account can be represented by a Record. At a high level, a Record is similar to UTXOs in the Bitcoin network. A Transition in a transaction can consist of multiple input and output Records. As Aleo is a privacy platform, each Record undergoes encryption before being sent in a transaction. Before diving into the encryption of Records, let’s first introduce Transitions. The data structure of Transition is defined in synthesizer/src/block/transition/mod.rs.
pub struct Transition<N: Network> {
/// The transition ID.
id: N::TransitionID,
/// The program ID.
program_id: ProgramID<N>,
/// The function name.
function_name: Identifier<N>,
/// The transition inputs.
inputs: Vec<Input<N>>,
/// The transition outputs.
outputs: Vec<Output<N>>,
/// The inputs for finalize.
finalize: Option<Vec<Value<N>>>,
/// The transition proof.
proof: Proof<N>,
/// The transition public key.
tpk: Group<N>,
/// The transition commitment.
tcm: Field<N>,
}Inputs and outputs of a Transition consist of lists of input/output Records. The proof is the logical proof for the Transition (a sub-function with state transitions). By the way, a transaction can consist of multiple Transitions. Next, let’s explain in detail what tpk represents.
As mentioned earlier, a Transaction is “composed” of multiple Transitions. The on-chain records contain encrypted information and proofs of multiple Transitions. Each Transition’s execution requires user signatures and is represented by a Request. One or more Requests form an Authorization.
pub struct Request<N: Network> {
/// The request caller.
caller: Address<N>,
/// The network ID.
network_id: U16<N>,
/// The program ID.
program_id: ProgramID<N>,
/// The function name.
function_name: Identifier<N>,
/// The input ID for the transition.
input_ids: Vec<InputID<N>>,
/// The function inputs.
inputs: Vec<Value<N>>,
/// The signature for the transition.
signature: Signature<N>,
/// The tag secret key.
sk_tag: Field<N>,
/// The transition view key.
tvk: Field<N>,
/// The transition secret key.
tsk: Scalar<N>,
/// The transition commitment.
tcm: Field<N>,
}Each Request corresponds to a Response:
pub struct Response<N: Network> {
/// The output ID for the transition.
output_ids: Vec<OutputID<N>>,
/// The function outputs.
outputs: Vec<Value<N>>,
}The signing algorithm for Request/Transition is the same as the aforementioned signature algorithm. For Transition signing, the content of the message is as follows. The implementation code can be found in console/program/src/request/sign.rs within the sign function.
Now let’s take a look at the encryption process of Records.
The encryption logic for Records is implemented in console/program/src/data/record/encrypt.rs within the encrypt function:
rustCopy code
pub fn encrypt(&self, randomizer: Scalar<N>) -> Result<Record<N, Ciphertext<N>>> {The decryption logic for Records is implemented in console/program/src/data/record/decrypt.rs within the decrypt function:
rustCopy code
pub fn decrypt(&self, view_key: &ViewKey<N>) -> Result<Record<N, Plaintext<N>>> {The detailed encryption process is as follows:
Each Transition has a unique tvk. When an authorized user views Records, the system will determine whether the user has access rights based on their view_key.
What’s AVM?
AVM stands for Aleo Virtual Machine. It is a stack machine that executes specific functions within the stack. The main logic involves constructing a complete arithmetic circuit (R1CS) from each instruction in the function. After constructing the R1CS, corresponding proofs are generated using the Marlin algorithm.
The detailed implementation can be found in the execute_function function in synthesizer/src/process/stack/execute.rs. Let's take a closer look at what the execution of a specific function proves.
Each transaction has an inclusion proof that ensures the correctness of the input information. Other logical proofs are included in the proof field of the Transition, proving the correctness of a specific Transition's logic.
This is a brief overview of the AVM design and its key components. You can find more detailed information and implementation code in the GitHub repository provided.
