Device Provisioning and Linking

Cryptid’s two-layer identity system enables seamless multi-device support. Your User Identity remains constant across all devices, while each device maintains its own Device Identity for MLS operations.

Note

Device IDs are cryptographically derived from public keys (device_id = Blake3(public_key)). See Cryptid’s Identity System for details on device identity generation.

This page will cover:

• Verifiable Delay Function (VDF) for first-time device announcements
• Initial device setup (first device)
• Linking additional devices via QR codes
• Syncing new devices to existing groups
• Security considerations

Verifiable Delay Function (VDF) for First-Time Announcements

To prevent spam and sockpuppet attacks, first-time device announcements require a Verifiable Delay Function (VDF). This is essentially a cryptographic proof that you spent time (not just CPU cycles) on a task.

Why use a VDF?

• Hardware-independent: FPGAs/ASICs provide no advantage (forced sequential computation)
• Time-based: Everyone takes approximately the same time
• Fair: Can’t “buy” your way past it with expensive hardware
• Simple: Uses only SHA256 hashing
• Mobile-friendly: Works efficiently on phones and tablets

Note

Technical Note: This version of the spec uses sequential hashing, which is technically a Proof of Sequential Work rather than a true VDF.

In a true VDF, verification is significantly faster than generation. Our approach with sequential hashing requires the server to re-compute the entire hash chain for verification, taking the same time as generation.

We mitigate the verification cost through aggressive rate limiting, making the server DoS risk manageable.

Why we call it “VDF” in the code: We use VDF terminology thoughout the codebase to minimize future spec changes when we migrate to a true VDF implementation (e.g., Wesolowski or Pietrzak) in v2.0, which will provide fast verification while maintaining the same API surface.

Algorithm: Sequential Hash Chain

A VDF is computed by applying SHA256 sequentially. This makes each hash depend on the hash before it, making parallelization impossible:

struct VDF {
    input: [u8; 64],  // challenge || public_key
    iterations: u64,  // Number of sequential hash operations
    output: [u8; 32], // Final hash after all iterations
}

impl VDF {
    /// Generate VDF proof (client-side)
    fn generate(
        challenge: &[u8; 32],
        public_key: &Ed25519PublicKey,
        iterations: u64,
    ) -> Self {
        // Combine challenge and public key as input
        let mut input = [0u8; 64];
        input[..32].copy_from_slice(challenge);
        input[..32].copy_from_slice(public_key.as_bytes());

        // Start with hash of input
        let mut state = sha256(&input);

        // Apply SHA256 sequentially
        // Each iteration depends on the previous result
        for _ in 0..iterations {
            state = sha256(&state);
        }

        VDF {
            input,
            iterations,
            output: state,
        }
    }

    /// Verify VDF proof (server-side)
    fn verify(&self) -> bool {
        // Re-compute the hash chain
        let mut state = sha256(&self.input);

        for _ in 0..self.iterations {
            state = sha256(&state);
        }

        // Check if the final hash matches
        state == self.output
    }
}

Note

VDF is only required for first-time device announcement. Subsequent operations use JWT authentication.

DoS Mitigation Strategy

Since server verification requires re-computing the hash chain (same cost as generation), we use aggressive rate limiting to prevent DoS attacks.

Rate Limiting Configuration

// First-time announcement limit
const MAX_CHALLENGES_PER_IP_PER_HOUR: u8 = 10;
const MAX_ANNOUNCEMENTS_PER_IP_PER_HOUR: u8 = 3;
const MAX_ANNOUNCEMENTS_PER_IP_PER_DAY: u8 = 10;

// Ban invalid proofs
const BAN_DURATION_INVALID_PROOF: Duration = Duration::hours(24);

Rate Limit Enforcement Order

It is critical to note that rate limits are checked before expensive VDF verification.

async fn handle_announce(
    request: AnnounceRequest,
    state: &ServerState,
    client_ip: IpAddr,
) -> Result<AnnounceResponse> {
    let is_first_time = !device_exists(&request.device_id);

    if is_first_time {
        // 1. Check rate limits first
        let rate_limit_key = format!("announce:{client_ip}");
        let attempts_hour = get_rate_limit_count(&rate_limit_key, 3600)?;
        let attempts_day = get_rate_limit_count(&rate_limit_key, 86400)?;

        if attempts_hour >= MAX_ANNOUNCEMENTS_PER_IP_PER_HOUR {
            return Err("Rate limit exceeded: max 3 announcements per hour");
        }

        if attempts_day >= MAX_ANNOUNCEMENTS_PER_IP_PER_DAY {
            return Err("Rate limit exceeded: max 10 announcements per day");
        }

        // 2. Increment rate limit counter
        increment_rate_limit(&rate_limit_key)?;

        // 3. NOW verify the VDF (can only be triggered 3 times / hour)
        let vdf = request.vdf_proof.ok_or("VDF proof required")?;

        if !vdf.verify() {
            // Invalid proof - ban IP and don't count against device limit
            ban_ip(&client_ip, BAN_DURATION_INVALID_PROOF);
            return Err("Invalid VDF proof");
        }

        // Continue with registration...
    }

    // Rest of the function...
}

DoS Protection

• Attackers are limited to 3 verifications per IP per hour and 10 verifications per IP per day
• Invalid proofs result in 24-hour IP ban

Initial Device Setup

When opening Cryptid for the first time, your device generates both identities and requests a delivery address from the server:

fn initial_device_setup(server: &str) -> Result<LocalIdentities> {
    // 1. Generate User Identity (shared across all your devices)
    let user_identity = UserIdentity::generate();

    // 2. Generate Device Identity (unique to THIS device)
    let mut device_identity = DeviceIdentity::generate();

    // 3. Request challenge from server
    let challenge_response = request_challenge(server)?;

    // 4. Generate VDF proof
    println!("Preparing device registration (this may take a few seconds)...");

    let vdf = VDF::generate(
        &challenge_response.challenge,
        &device_identity.keypair.public_key(),
        challenge_response.iterations,
    );

    println!("Registration proof generated!");

    // 5. Announce device
    let announce_response = announce_device_to_server(
        server,
        &device_identity,
        vdf,
    )?;

    // 6. Store server-generated delivery address
    device_identity.delivery_addresses.push(DeliveryAddress {
        prefix: announce_response.delivery_address.prefix,
        server: server.to_string(),
        created_at: announce_response.delivery_address.created_at,
        active: true,
    });

    // 7. Generate and upload KeyPackages
    let keypackage_bundles = device_identity.generate_key_packages(100);
    upload_keypackages(
        server,
        &device_identity.device_id,
        &keypackage_bundles,
        &announce_response.access_token
    )?;

    // 8. Store identities and access token
    Ok(LocalIdentities {
        user_identity,
        device_identity,
        access_token: announce_response.access_token,
    })
}

Step 1: Request Challenge

fn request_challenge(
    server: &str,
    device: &DeviceIdentity,
) -> Result<ChallengeResponse> {
    let request = ChallengeRequest {
        public_key: device.keypair.public_key(),
    }

    // POST /api/v1/announce/challenge
    http_get(&format!("https://{server}/api/v1/announce/challenge"), &request)
}

struct ChallengeResponse {
    challenge: [u8; 32], // Server-generated random challenge
    iterations: u64,     // Required VDF iterations (e.g., 5,000,000)
    expires_at: u64,     // Challenge expires after 5 minutes
}

Server generates challenge:

struct ChallengeRequest {
    public_key: Ed25519PublicKey,
}

async fn handle_challenge_request(
    state: &ServerState,
    client_ip: IpAddr,
    request: ChallengeRequest,
) -> Result<ChallengeResponse> {
    let device_id = Blake3(request.public_key.as_bytes());

    // Rate limit challenge requests
    let rate_limit_key = format("challenge:{client_ip}");
    let attempts = get_rate_limit_count(&rate_limit_key, 3600)?;

    if attempts >= MAX_CHALLENGES_PER_IP_PER_HOUR {
        return Err("Rate limit exceeded: max 3 challenges per hour");
    }

    increment_rate_limit(&rate_limit_key)?;

    // Generate challenge
    let challenge = generate_random(32);
    let iterations = calculate_vdf_iterations(state);
    let expires_at = current_unix_timestamp() + 300; // 5 minutes

    store_challenge(ChallengeRecord {
        challenge,
        device_public_key: request.public_key,
        iterations,
        created_at: current_unix_timestamp(),
        expires_at,
        used: false,
    })?;

    Ok(ChallengeResponse {
        challenge,
        iterations,
        expires_at,
    })
}

/// Server dynamically adjusts how many iterations clients must compute based on
/// current registration load
fn calculate_vdf_iterations(state: &ServerState) -> u64 {
    let base_iterations = 5_000_000u64; // 5M baseline
    let announcements_last_hour = get_announcements_count_last_hour();
    let target = 1000; // Expected 1000 registrations per hour

    // Increase difficulty based on load
    if announcements_last_hour > target * 2 {
        base_iterations * 16  // >2000/hour
    } else if announcements_last_hour > target * 3 / 2 {
        base_iterations * 8   // >1500/hour
    } else if announcements_last_hour > target {
        base_iterations * 4   // >1000/hour
    } else {
        base_iterations       // <= 1000/hour
    }
}

Step 2: Announce Device with VDF Proof

fn announce_device_to_server(
    server: &str,
    device: &DeviceIdentity,
    vdf: Vdf,
) -> Result<AnnounceResponse> {
    let timestamp = current_unix_timestamp();
    let message = format!("{}:{}", hex::encode(&device.device_id), timestamp);
    let signature = device.keypair.sign(message.as_bytes());

    let request = AnnounceRequest {
        device_id: device.device_id,
        public_key: device.keypair.public_key(),
        signature,
        timestamp,
        vdf_proof: Some(vdf)
    };

    http_post(&format!("https://{server}/api/v1/announce"), &request)
}

struct AnnounceRequest {
    device_id: DeviceId,
    public_key: Ed25519PublicKey,
    signature: Ed25519Signature,
    timestamp: u64,
    vdf_proof: Option<VDF>, // Required for first time announcements
}

struct AnnounceResponse {
    status: String,
    device_id: DeviceId,
    delivery_address: GeneratedAddress,
    access_token: String,
    expires_at: u64,
}

struct GeneratedAddress {
    full_address: String, // "x9y8z7w6v5u4...@example.com"
    prefix: Uuid, // "x9y8z7w6v5u4..."
    created_at: u64,
}

Server Verification with Rate Limiting

use uuid::Uuid;

async fn handle_announce(
    request: AnnounceRequest,
    state: &ServerState,
    client_ip: IpAddr,
) -> Result<AnnounceResponse> {
    // 1. Verify device_id is derived from public key
    let expected_device_id = Blake3(request.public_key.as_bytes());
    if request.device_id != expected_device_id {
        return Err("device_id must be Blake3(public_key)");
    }

    // 2. Check if first-time announcement
    let is_first_time = !device_exists(&request.device_id);

    // 3. Verify VDF with rate limiting if first time
    if is_first_time {
        // CRITICAL: Check rate limits BEFORE verification
        let rate_limit_key = format!("announce:{}", client_ip);
        let attempts_hour = get_rate_limit_count(&rate_limit_key, 3600)?;
        let attempts_day = get_rate_limit_count(&rate_limit_key, 86400)?;

        if attempts_hour >= MAX_ANNOUNCEMENTS_PER_IP_PER_HOUR {
            return Err("Rate limit exceeded: max 3 announcements per hour");
        }

        if attempts_day >= MAX_ANNOUNCEMENTS_PER_IP_PER_DAY {
            return Err("Rate limit exceeded: max 10 announcements per day");
        }

        // Increment rate limit
        increment_rate_limit(&rate_limit_key)?;

        // Get and verify VDF
        let vdf = request.vdf_proof
            .ok_or("VDF proof required")?;

        let challenge_record = get_challenge_for_vdf(&vdf)
            .ok_or("Invalid or expired challenge")?;

        if challenge_record.device_public_key != request.public_key {
            return Err("Challenge was issued to a different device");
        }

        if current_unix_timestamp() > challenge_record.expires_at {
            return Err("Challenge expired");
        }

        if challenge_record.used {
            return Err("Challenge already used");
        }

        // Verify VDF input
        let mut expected_input = [0u8; 64];
        expected_input[..32].copy_from_slice(&challenge_record.challenge);
        expected_input[32..].copy_from_slice(request.public_key.as_bytes());

        if vdf.input != expected_input {
            return Err("VDF input mismatch");
        }

        if vdf.iterations != challenge_record.iterations {
            return Err("VDF iterations mismatch");
        }

        // Verify VDF proof (re-compute hash chain)
        if !vdf.verify() {
            // Invalid proof - ban IP
            ban_ip(&client_ip, BAN_DURATION_INVALID_PROOF);
            return Err("Invalid VDF proof");
        }

        mark_challenge_used(&challenge_record.challenge)?;
    }

    // 4. Verify signature
    let message = format!("{}:{}", hex::encode(&request.device_id), request.timestamp);
    if !request.public_key.verify(&request.signature, message.as_bytes()) {
        return Err("Invalid signature");
    }

    // 5. Verify timestamp is recent
    if current_unix_timestamp() - request.timestamp > 300 {
        return Err("Timestamp is too old");
    }

    // 6. Generate delivery address
    let prefix = Uuid::new_v4();
    let full_address = format!("{prefix}@{}", state.server_domain);
    let delivery_address = GeneratedAddress {
        full_address,
        prefix,
        created_at: current_unix_timestamp(),
    };

    // 7. Register Address
    register_address(AddressRecord {
        prefix: prefix.clone(),
        device_id: request.device_id,
        public_key: request.public_key,
        created_at: current_unix_timestamp(),
        active: true,
    })?;

    // 8. Register Device
    if is_first_time {
        register_device(DeviceRecord {
            device_id: request.device_id,
            public_key: request.public_key,
            registered_at: current_unix_timestamp(),
        })?;
    }

    // 9. Issue JWT token
    let access_token = issue_jwt_token(&request.device_id, &request.public_key)?;

    Ok(AnnounceResponse {
        status: "success".to_string(),
        device_id: request.device_id,
        delivery_address,
        access_token,
        expires_at: current_unix_timestamp() + 86400,
    })
}

Linking Additional Devices

When adding another device, the new device receives a copy of your User Identity from an existing device.

Step 1: New Device Initiates Provisioning

fn initiate_device_linking(server: &str) -> Result<ProvisioningSession> {
    let device_identity = DeviceIdentity::generate();
    let ephemeral_keypair = Ed25519KeyPair::generate();

    let provisioning_response = request_provisioning_address(
        server,
        &ephemeral_keypair.public_key(),
        300, // expires in 5 minutes
    )?;

    let qr_data = ProvisioningRequest {
        ephemeral_public_key: ephemeral_keypair.public_key(),
        provisioning_address: provisioning_response.address.clone(),
        server: server.to_string(),
        expires_at: provisioning_response.expires_at,
    };

    Ok(ProvisioningSession {
        device_identity,
        ephemeral_keypair,
        provisioning_address: provisioning_response.provisioning_address,
        qr_code: generate_qr_code(&qr_data)?,
        expires_at: provisioning_response.expires_at,
    })
}

fn request_provisioning_address(
    server: &str,
    ephemeral_pubkey: &Ed25519PublicKey,
    ttl_seconds: u64,
) -> Result<ProvisioningAddressResponse> {
    let request = ProvisoningAddressRequest {
        ephemeral_public_key: *ephemeral_pubkey,
        ttl_seconds,
        timestamp: current_unix_timestamp(),
    };

    http_post(u
        &format!("https://{server}/api/v1/provisioning/create"),
        &request,
    )
}

Note

Provisioning address are temporary (5 min TTL) and automatically deleted by the server after use or expiration.

Step 2: Existing Device Scans QR

fn provision_new_device(
    existing_device: &LocalIdentities,
    qr_data: &ProvisioningRequest,
) -> Result<()> {
    if current_unix_timestamp() > qr_data.expires_at {
        return Err("Provisioning request expired");
    }

    let user_identity_data = ProvisioningPayload {
        user_id: existing_device.user_identity.user_id,
        user_keypair: existing_device.user_identity.keypair.clone(),
        linked_devices: existing_device.user_identity.linked_devices.clone(),
        default_persona: provisioning_payload.default_persona,
        personas: provisioning_payload.personas,
        created_at: existing_device.user_identity.created_at,
    };

    let serialized = serialize(&user_identity_data)?;
    let encrypted_blob = encrypt_with_public_key(
        &qr_data.ephemeral_public_key,
        &serialized,
    )?;

    send_provisioning_blob(
        &qr_data.server,
        &qr_data.provisioning_address,
        encrypted_blob,
    )
}

Step 3: New Device Receives User Identity

fn complete_device_linking(
    session: &ProvisioningSession,
    server: &str,
) -> Result<LocalIdentities> {
    let encrypted_blob = poll_provisioning_address(
        &session.provisioning_address,
        Duration::from_secs(60),
    )?;

    let decrypted = decrypt_with_private_key(
        &session.ephemeral_keypair.private_key(),
        &encrypted_blob,
    )?;

    let provisioning_payload: ProvisioningPayload = deserialize(&decrypted)?;

    let user_identity = UserIdentity {
        userid: provisioning_payload.userid,
        keypair: provisioning_payload.user_keypair,
        linked_devices: provisioning_payload.linked_devices,
        created_at: provisioning_payload.created_at,
        default_persona: provisioning_payload.default_persona,
        personas: provisioning_payload.personas,
    };

    secure_erase(&session.ephemeral_keypair.private_key());

    complete_linked_device_setup(
        user_identity,
        session.device_identity.clone(),
        server
    )
}

fn complete_linked_device_setup(
    user_identity: UserIdentity,
    mut device_identity: DeviceIdentity,
    server: &str,
) -> Result<LocalIdentities> {
    // Announce device
    let announce_response = announce_device_to_server(
        server,
        &device_identity,
    );

    device_identity.delivery_addresses.push(DeliveryAddress {
        prefix: announce_response.delivery_address.prefix,
        server: server.to_string(),
        created_at: announce_response.delivery_address.created_at,
        active: true,
    });

    let keypackage_bundles = device_identity.generate_key_packages(100);
    upload_keypackages(
        server,
        &device_identity.device_id,
        &keypackage_bundles,
        &announce_response.access_token,
    )?;

    Ok(LocalIdentities {
        user_identity,
        device_identity,
        access_token: announce_response.access_token,
    })
}

Address Rotation

fn rotate_delivery_address(
    device: &mut DeviceIdentity,
    server: &str,
    access_token: &str,
) -> Result<String> {
    let response = announce_device_to_server_authenticated(
        server,
        &device.device_id,
        access_token,
    )?;

    let new_addr = &response.delivery_address;
    device.delivery_addresses.push(DeliveryAddress {
        prefix: new_addr.prefix.clone(),
        server: server.to_string(),
        created_at: new_addr.created_at,
        active: true,
    });

    Ok(new_addr.full_address.clone())
}

Syncing New Devices to Existing Groups

async fn sync_new_device_to_groups(
    new_device_info: &DevicePublicInfo,
    existing_device: &DeviceIdentity,
    user_groups: &Vec<MultiUserGroup>,
    provider: &impl OpenMlsProvider,
) -> Result<SyncResult> {
    let mut synced_groups = Vec::new();
    let mut failed_groups = Vec::new();

    let keypackage = fetch_keypackage(
        &new_device_info.keypackage_server,
        &new_device_info.device_id,
    )?;

    for group in user_groups {
        // Extract permission extension from MLS group context
        let perm_result = get_permission_extension(&group.mls_state);

        let permissions = match perm_result {
            Ok(perms) => perms,
            Err(e) => {
                failed_groups.push((group.group_id, format!("Failed to read permissions: {e}")));
                continue;
            }
        };

        // Check if existing device is in the group's permissions
        let device_perms = match permissions.device_permissions.get(&existing_device.device_id) {
            Some(perms) => perms,
            None => {
                failed_groups.push((group.group_id, "Device not found in group permissions"));
                continue;
            }
        }

        // Verify permission - needs either INVITE_MEMBERS or ADMINISTRATOR
        if !device_perms.contains(Permissions::INVITE_MEMBERS) && !device_perms.contains(Permissions::ADMINISTRATOR) {
            failed_groups.push((group.group_id, "Insufficient permissions: requires INVITE_MEMBERS or ADMINISTRATOR"));
            continue;
        }

        // Attempt to add device to group
        match add_device_to_group(group, &keypackage, existing_device, provider) {
            Ok(_) => synced_groups.push(group.group_id),
            Err(e) => failed_groups.push((group.group_id, e.to_string())),
        }
    }

    Ok(SyncResult {
        synced_groups,
        failed_groups,
    })
}

Security Considerations

VDF Security

Prevents Sockpuppet Attacks:

• 10,000 devices at 5M iterations
• Adaptive iterations up to 48M during attacks

DoS Mitigation

Rate limiting protects servers:

• Maximum 3 verifications per IP per hour = 3 seconds CPU per hour per IP
• Invalid proofs result in 24-hour IP ban
• Even with 1000 different IPs: 3000 seconds spread over 1 hour = manageable load

Attack scenario analysis:

• Attacker with 1000 IPs
• 3 announcements each = 3000 verifications
• Spread over 1 hour = 50 verifications per minute average
• Server handles easily with modern CPU

Derived Device ID Security

device_id is cryptographically bound to public key via Blake3(public_key).

See Identity System for details.

Rate Limiting Configuration

// VDF iterations (sequential SHA256)
const BASE_VDF_ITERATIONS: u64 = 5_000_000;
const MAX_VDF_ITERATIONS: u64 = 80_000_000;

// Rate limits (STRICT for DoS protection)
const MAX_CHALLENGES_PER_IP_PER_HOUR: usize = 10;
const MAX_ANNOUNCEMENTS_PER_IP_PER_HOUR: usize = 3;
const MAX_ANNOUNCEMENTS_PER_IP_PER_DAY: usize = 10;

// Bans
const BAN_DURATION_INVALID_PROOF: Duration = Duration::hours(24);

// Address limits
const MAX_ADDRESSES_PER_DEVICE: usize = 100;

// Provisioning limits
const MAX_PROVISIONING_PER_IP_PER_HOUR: usize = 10;

Best Practices

For Users

1. First-time setup: Expect 1-5 second delay for VDF (one-time only)
2. Link devices in private: Prevent shoulder surfing during QR scanning
3. Monitor linked devices: Regular review of device list

For Server Operators

1. Monitor rate limits: Track IPs hitting limits
2. Monitor ban list: Review banned IPs periodically
3. Adjust iterations: Increase during detected attacks
4. Log invalid proofs: Track patterns of abuse
5. Consider IP allowlisting: For trusted networks

For Implementations

1. Show VDF progress: Display “Preparing registration…” message
2. Use blake3 crate: Optimized Blake3 implementation
3. Enforce rate limits: Check BEFORE expensive operations
4. Ban invalid proofs: Immediate 24h ban for fake proofs
5. Log security events: Track all VDF attempts and failures

Note

Future Enhancement: For v2.0, I’m considering migrating to a VDF with fast verification (e.g., Wesolowski) when stable Rust implementations are available. The current approach is designed to be easily upgradeable.

There is currently a crate called vdf, but it seems to be unmaintained. I might fork it and take over maintainance at some point if I go in this direction.