mirror of https://github.com/selfxyz/self.git synced 2026-02-19 02:24:25 -05:00

Files

Justin Hernandez 466fd5d8e7 update kmp specs (#1757 )

* save new specs

* rename specs

2026-02-16 00:42:06 -08:00

53 KiB

Raw Permalink Blame History

Common KMP Library — Port `@selfxyz/common` Utilities to Pure Kotlin

Overview

Port the core math, cryptographic hashing, tree operations, passport parsing, and certificate parsing from TypeScript (common/src/utils/) to pure Kotlin in commonMain. This library has zero platform dependencies — no expect/actual, no Android/iOS APIs. Everything is pure Kotlin math that compiles for JVM, iOS, JS, and WASM targets.

This is the foundation layer that both SPEC-PROVING-CLIENT.md and a future browser extension depend on.

Prerequisites: None (this is the leaf dependency).

Why Pure `commonMain`

Every function in this library is deterministic math: hash bytes, build trees, parse ASN.1, pack field elements. None of it touches platform APIs (no file system, no networking, no UI). By keeping it in commonMain as pure Kotlin:

Adding jsMain or wasmMain later for a browser extension costs zero porting effort for this layer
Unit tests run on JVM (commonTest) with fast iteration
Identical outputs are guaranteed across all platforms

The only exception is SHA hashing (SHA-1, SHA-256, SHA-384, SHA-512) which could use platform implementations for performance, but a pure Kotlin implementation works fine and avoids any expect/actual complexity.

Module Structure

packages/kmp-sdk/shared/src/commonMain/kotlin/xyz/self/sdk/common/
  hash/
    Poseidon.kt                   — Poseidon hash (1–16 input variants)
    PoseidonConstants.kt          — Round constants and mixing matrices (BN254)
    FlexiblePoseidon.kt           — Dynamic variant selection + chunked hashing
    Sha.kt                        — SHA-1/224/256/384/512 (pure Kotlin or expect/actual)
    ShaPad.kt                     — SHA padding for circuit inputs
  math/
    BigIntField.kt                — Field arithmetic over BN254 prime
    BytePacking.kt                — packBytes, splitToWords, hexToDecimal, num2Bits
  trees/
    LeanIMT.kt                    — Lean Incremental Merkle Tree (import, indexOf, generateProof)
    SparseMerkleTree.kt           — Sparse Merkle Tree (import, add, createProof)
    MerkleProof.kt                — Proof data structures
    LeafGenerators.kt             — OFAC leaf functions (name, DOB, country, passport number)
    TreeConstants.kt              — Depth constants
  passport/
    PassportDataParser.kt         — initPassportDataParsing (metadata extraction)
    MrzFormatter.kt               — formatMrz (DER/TLV encoding)
    CommitmentGenerator.kt        — generateCommitment (Poseidon-5)
    NullifierGenerator.kt         — generateNullifier
    DscLeaf.kt                    — getLeafDscTree (DSC + CSCA leaf hashing)
    SelectorGenerator.kt          — getSelectorDg1 (attribute → MRZ position mapping)
    SignatureExtractor.kt         — Extract r,s from DER-encoded ECDSA signatures
  certificate/
    Asn1Parser.kt                 — Minimal ASN.1 DER parser (Tag-Length-Value)
    X509CertificateParser.kt      — parseCertificateSimple → CertificateData
    OidResolver.kt                — OID → algorithm/curve name mapping
    CscaLookup.kt                 — getCSCAFromSKI (find issuer cert by SKI)
  models/
    CertificateData.kt            — Parsed certificate with pub key details
    PassportMetadata.kt           — Metadata extracted from passport data
    FieldElement.kt               — BigInt wrapper for BN254 field elements
  constants/
    Constants.kt                  — Tree depths, max padded sizes, attestation IDs
    SkiPem.kt                     — SKI → CSCA PEM mapping (prod + staging)

Test mirror:

packages/kmp-sdk/shared/src/commonTest/kotlin/xyz/self/sdk/common/
  hash/
    PoseidonTest.kt               — Known test vectors from poseidon-lite
    FlexiblePoseidonTest.kt       — packBytesAndPoseidon roundtrips
    ShaPadTest.kt                 — Padding output verification
  math/
    BytePackingTest.kt            — packBytes, splitToWords test vectors
  trees/
    LeanIMTTest.kt                — Import, indexOf, generateProof
    SparseMerkleTreeTest.kt       — Add, createProof, membership/non-membership
    LeafGeneratorsTest.kt         — Known leaf values
  passport/
    PassportDataParserTest.kt     — Parse mock passports, verify metadata
    CommitmentGeneratorTest.kt    — Known commitment hashes
    MrzFormatterTest.kt           — TLV encoding verification
  certificate/
    Asn1ParserTest.kt             — Parse known DER structures
    X509CertificateParserTest.kt  — Parse real DSC/CSCA certificates

Detailed Component Specs

1. Poseidon Hash

Port of poseidon-lite npm package. The Poseidon hash operates over the BN254 scalar field.

Field Prime

object BN254 {
    val PRIME = "21888242871839275222246405745257275088548364400416034343698204186575808495617".toBigInteger()
}

Algorithm

/**
 * Poseidon hash function over BN254 field.
 *
 * @param inputs 1–16 field elements
 * @return Single field element hash
 */
fun poseidon(inputs: List<BigInteger>): BigInteger {
    require(inputs.size in 1..16) { "Poseidon supports 1-16 inputs, got ${inputs.size}" }

    val t = inputs.size + 1  // State width = inputs + capacity
    val nRoundsF = 8         // Full rounds (4 before + 4 after partial rounds)
    val nRoundsP = PARTIAL_ROUNDS[inputs.size - 1]  // Varies by input count

    // Initialize state: [0, input_0, input_1, ..., input_n]
    val state = mutableListOf(BigInteger.ZERO)
    state.addAll(inputs.map { it.mod(BN254.PRIME) })

    val C = getRoundConstants(t)  // Round constants for width t
    val M = getMixingMatrix(t)    // MDS mixing matrix for width t

    for (round in 0 until nRoundsF + nRoundsP) {
        // Add round constants
        for (i in 0 until t) {
            state[i] = (state[i] + C[round * t + i]).mod(BN254.PRIME)
        }

        // S-box: x^5 mod p
        if (round < nRoundsF / 2 || round >= nRoundsF / 2 + nRoundsP) {
            // Full round: apply S-box to all elements
            for (i in 0 until t) {
                state[i] = pow5(state[i])
            }
        } else {
            // Partial round: apply S-box only to first element
            state[0] = pow5(state[0])
        }

        // Linear mixing: state = M * state
        val newState = MutableList(t) { BigInteger.ZERO }
        for (i in 0 until t) {
            for (j in 0 until t) {
                newState[i] = (newState[i] + M[i][j] * state[j]).mod(BN254.PRIME)
            }
        }
        for (i in 0 until t) state[i] = newState[i]
    }

    return state[0]  // Output is first element
}

private fun pow5(v: BigInteger): BigInteger {
    val v2 = (v * v).mod(BN254.PRIME)
    return (v * v2 * v2).mod(BN254.PRIME)
}

Round Constants

Partial rounds per input count (from poseidon-lite):

val PARTIAL_ROUNDS = intArrayOf(
    56, 57, 56, 60, 60, 63, 64, 63, 60, 66, 60, 65, 70, 60, 64, 68
)
// Index 0 = poseidon1 (56 partial rounds)
// Index 1 = poseidon2 (57 partial rounds)
// ...
// Index 15 = poseidon16 (68 partial rounds)

The round constants (C) and mixing matrices (M) are large — ~50KB of BigInteger constants total. These are generated by the Grain LFSR:

generate_parameters_grain.sage 1 0 254 {t} 8 {nRoundsP} 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001

Implementation approach: Store constants as base64-encoded strings in PoseidonConstants.kt (matching poseidon-lite's format), decode lazily on first use.

Convenience Functions

fun poseidon2(a: BigInteger, b: BigInteger): BigInteger = poseidon(listOf(a, b))
fun poseidon3(a: BigInteger, b: BigInteger, c: BigInteger): BigInteger = poseidon(listOf(a, b, c))
fun poseidon5(inputs: List<BigInteger>): BigInteger = poseidon(inputs)
// ... poseidon1 through poseidon16

`flexiblePoseidon` and `packBytesAndPoseidon`

/**
 * Dynamically selects Poseidon variant based on input count.
 */
fun flexiblePoseidon(inputs: List<BigInteger>): BigInteger {
    require(inputs.size in 1..16) { "flexiblePoseidon supports 1-16 inputs" }
    return poseidon(inputs)
}

/**
 * Pack byte array into field elements and hash with Poseidon.
 * Bytes are chunked into 31-byte groups, each becoming a field element.
 * If >16 chunks, uses chunked hashing (poseidon16 per group, then combine).
 *
 * Port of packBytesAndPoseidon from common/src/utils/hash.ts
 */
fun packBytesAndPoseidon(bytes: List<Int>): BigInteger {
    val packed = packBytesArray(bytes)
    return customHasher(packed)
}

/**
 * Chunked Poseidon hashing for large inputs.
 * For ≤16 elements: direct flexiblePoseidon
 * For >16 elements: chunk into groups of 16, hash each, then hash results
 */
fun customHasher(elements: List<BigInteger>): BigInteger {
    if (elements.size <= 16) {
        return flexiblePoseidon(elements)
    }

    val chunks = elements.chunked(16)
    val chunkHashes = chunks.map { chunk ->
        if (chunk.size == 16) poseidon(chunk)
        else flexiblePoseidon(chunk)
    }

    return if (chunkHashes.size <= 16) {
        flexiblePoseidon(chunkHashes)
    } else {
        customHasher(chunkHashes)  // Recursive for very large inputs
    }
}

Testing

class PoseidonTest {
    @Test
    fun `poseidon2 known vector`() {
        // Generate test vectors by running the TypeScript:
        //   import { poseidon2 } from 'poseidon-lite'
        //   console.log(poseidon2([1n, 2n]).toString())
        val result = poseidon2(BigInteger.ONE, BigInteger.TWO)
        assertEquals("7853200120776062878684798364095072458815029376092732009249414926327459813530".toBigInteger(), result)
    }

    @Test
    fun `poseidon5 known vector`() {
        val result = poseidon5(listOf(1, 2, 3, 4, 5).map { it.toBigInteger() })
        // Compare with TypeScript output
        assertEquals(EXPECTED_POSEIDON5_VECTOR, result)
    }

    @Test
    fun `packBytesAndPoseidon matches TypeScript`() {
        // Test with known MRZ bytes
        val mrzBytes = "P<FRADUPONT<<JEAN<<<<<<<<<<<<<<<<<<<<<<<<<<<".map { it.code }
        val result = packBytesAndPoseidon(mrzBytes)
        assertEquals(EXPECTED_MRZ_HASH, result)
    }

    @Test
    fun `poseidon field overflow wraps correctly`() {
        // Input larger than field prime should be reduced mod p
        val large = BN254.PRIME + BigInteger.ONE
        val result = poseidon2(large, BigInteger.ZERO)
        val expected = poseidon2(BigInteger.ONE, BigInteger.ZERO)
        assertEquals(expected, result)
    }
}

Test vector generation strategy: Write a small TypeScript script that computes all needed test vectors and outputs them as Kotlin constants. Run once, embed in test files.

2. Byte Packing Utilities

Port of common/src/utils/bytes.ts.

object BytePacking {
    const val MAX_BYTES_IN_FIELD = 31  // 31 bytes < 254 bits (BN254 field)

    /**
     * Pack a byte array into field elements (31 bytes each).
     * Each chunk is packed little-endian: byte[0] + byte[1]*256 + byte[2]*65536 + ...
     *
     * Port of packBytesArray from common/src/utils/bytes.ts
     */
    fun packBytesArray(unpacked: List<Int>): List<BigInteger> {
        val result = mutableListOf<BigInteger>()
        for (chunk in unpacked.chunked(MAX_BYTES_IN_FIELD)) {
            var packed = BigInteger.ZERO
            for ((i, byte) in chunk.withIndex()) {
                packed = packed + (byte.toBigInteger() shl (i * 8))
            }
            result.add(packed)
        }
        return result
    }

    /**
     * Split a BigInt into k words of n bits each.
     * Used for formatting RSA keys and signatures for circuit inputs.
     *
     * Port of splitToWords from common/src/utils/bytes.ts
     */
    fun splitToWords(number: BigInteger, wordSize: Int, numWords: Int): List<String> {
        val mask = (BigInteger.ONE shl wordSize) - BigInteger.ONE
        return (0 until numWords).map { i ->
            ((number shr (i * wordSize)) and mask).toString()
        }
    }

    /**
     * Convert hex string to decimal string.
     */
    fun hexToDecimal(hex: String): String {
        return BigInteger(hex, 16).toString()
    }

    /**
     * Convert hex string to signed byte array (values -128 to 127).
     */
    fun hexToSignedBytes(hex: String): List<Int> {
        val cleanHex = hex.removePrefix("0x")
        return cleanHex.chunked(2).map { it.toInt(16).toByte().toInt() }
    }

    /**
     * Convert number to n-bit binary array (LSB first).
     */
    fun num2Bits(numBits: Int, value: BigInteger): List<BigInteger> {
        return (0 until numBits).map { i ->
            (value shr i) and BigInteger.ONE
        }
    }

    /**
     * Convert byte array to decimal string via BigInt.
     */
    fun bytesToBigDecimal(bytes: List<Int>): String {
        var result = BigInteger.ZERO
        for (byte in bytes) {
            result = (result shl 8) + (byte and 0xFF).toBigInteger()
        }
        return result.toString()
    }
}

Testing

class BytePackingTest {
    @Test
    fun `packBytesArray packs 31 bytes into one field element`() {
        val bytes = (1..31).toList()
        val packed = BytePacking.packBytesArray(bytes)
        assertEquals(1, packed.size)
        // Verify: 1 + 2*256 + 3*65536 + ...
    }

    @Test
    fun `packBytesArray splits at 31-byte boundary`() {
        val bytes = (0..62).toList()  // 63 bytes = 3 chunks (31 + 31 + 1)
        val packed = BytePacking.packBytesArray(bytes)
        assertEquals(3, packed.size)
    }

    @Test
    fun `splitToWords decomposes RSA modulus correctly`() {
        val n = BigInteger("65537")
        val words = BytePacking.splitToWords(n, wordSize = 8, numWords = 4)
        assertEquals(listOf("1", "0", "1", "0"), words)  // 65537 = 0x10001
    }

    @Test
    fun `num2Bits converts correctly`() {
        val bits = BytePacking.num2Bits(8, BigInteger.valueOf(5))
        // 5 = 101 in binary, LSB first = [1, 0, 1, 0, 0, 0, 0, 0]
        assertEquals(BigInteger.ONE, bits[0])
        assertEquals(BigInteger.ZERO, bits[1])
        assertEquals(BigInteger.ONE, bits[2])
    }
}

3. SHA Padding

Port of common/src/utils/shaPad.ts. Used to prepare data for circuit SHA verification.

object ShaPad {
    /**
     * SHA-1/SHA-224/SHA-256 padding (512-bit blocks).
     *
     * 1. Append 0x80
     * 2. Pad with zeros until (length_bits + 64) % 512 == 0
     * 3. Append 64-bit big-endian message length
     * 4. Zero-pad to maxShaBytes
     *
     * @param message Input byte array
     * @param maxShaBytes Maximum padded output size
     * @return Pair of (padded bytes, actual message bit length)
     */
    fun shaPad(message: List<Int>, maxShaBytes: Int): Pair<List<Int>, Int> {
        val msgLen = message.size
        val bitLen = msgLen * 8

        val result = message.toMutableList()
        result.add(0x80)

        // Pad to 512-bit boundary (minus 64 bits for length)
        while ((result.size * 8 + 64) % 512 != 0) {
            result.add(0)
        }

        // Append 64-bit big-endian message length
        for (i in 56 downTo 0 step 8) {
            result.add((bitLen.toLong() shr i).toInt() and 0xFF)
        }

        // Zero-pad to maxShaBytes
        while (result.size < maxShaBytes) {
            result.add(0)
        }

        return Pair(result, bitLen)
    }

    /**
     * SHA-384/SHA-512 padding (1024-bit blocks).
     *
     * Same as shaPad but:
     * - Uses 128-bit message length
     * - Pads to 1024-bit block boundary
     */
    fun sha384_512Pad(message: List<Int>, maxShaBytes: Int): Pair<List<Int>, Int> {
        val msgLen = message.size
        val bitLen = msgLen * 8

        val result = message.toMutableList()
        result.add(0x80)

        // Pad to 1024-bit boundary (minus 128 bits for length)
        while ((result.size * 8 + 128) % 1024 != 0) {
            result.add(0)
        }

        // Append 128-bit big-endian message length (upper 64 bits are zero for our sizes)
        for (i in 0 until 8) result.add(0)  // Upper 64 bits
        for (i in 56 downTo 0 step 8) {
            result.add((bitLen.toLong() shr i).toInt() and 0xFF)
        }

        // Zero-pad to maxShaBytes
        while (result.size < maxShaBytes) {
            result.add(0)
        }

        return Pair(result, bitLen)
    }

    /**
     * Select correct padding function based on hash algorithm.
     */
    fun pad(hashAlgorithm: String): (List<Int>, Int) -> Pair<List<Int>, Int> {
        return when (hashAlgorithm.lowercase()) {
            "sha1", "sha224", "sha256" -> ::shaPad
            "sha384", "sha512" -> ::sha384_512Pad
            else -> throw IllegalArgumentException("Unsupported hash algorithm: $hashAlgorithm")
        }
    }
}

Testing

class ShaPadTest {
    @Test
    fun `sha256 padding appends 0x80 and length`() {
        val msg = listOf(0x61, 0x62, 0x63)  // "abc"
        val (padded, bitLen) = ShaPad.shaPad(msg, 64)
        assertEquals(24, bitLen)
        assertEquals(0x80, padded[3])
        // Last 8 bytes = 64-bit big-endian length = 24 = 0x18
        assertEquals(0x18, padded[63])
    }

    @Test
    fun `sha384 padding uses 1024-bit blocks`() {
        val msg = (0 until 100).map { it and 0xFF }
        val (padded, _) = ShaPad.sha384_512Pad(msg, 256)
        assertEquals(256, padded.size)
        // Verify block alignment
        assertTrue((padded.indexOf(0x80) * 8 + 128) <= padded.size * 8)
    }
}

4. LeanIMT (Lean Incremental Merkle Tree)

Port of @openpassport/zk-kit-lean-imt. Used for commitment tree and DSC tree lookups.

/**
 * Lean Incremental Merkle Tree — binary hash tree with ordered insertion.
 *
 * Serialization format: JSON object with "nodes" array of arrays of BigInt strings.
 * Level 0 = leaves, Level n = root.
 *
 * Used for:
 *   - Commitment tree: user registration lookups (depth 33)
 *   - DSC tree: document signing certificate lookups (depth 21)
 */
class LeanIMT(
    private val hashFn: (BigInteger, BigInteger) -> BigInteger,
) {
    private val nodes: MutableList<MutableList<BigInteger>> = mutableListOf()

    val root: BigInteger
        get() = if (nodes.isEmpty()) BigInteger.ZERO
                else nodes.last().firstOrNull() ?: BigInteger.ZERO

    val size: Int
        get() = if (nodes.isEmpty()) 0 else nodes[0].size

    /**
     * Find the index of a leaf in the tree.
     * @return Index (0-based) or -1 if not found
     */
    fun indexOf(leaf: BigInteger): Int {
        if (nodes.isEmpty()) return -1
        return nodes[0].indexOf(leaf)
    }

    /**
     * Generate an inclusion proof for a leaf at the given index.
     * @return MerkleProof with siblings and path indices
     */
    fun generateProof(index: Int): LeanIMTProof {
        require(index in 0 until size) { "Index $index out of range [0, $size)" }

        val siblings = mutableListOf<BigInteger>()
        val pathIndices = mutableListOf<Int>()
        var currentIndex = index

        for (level in 0 until nodes.size - 1) {
            val siblingIndex = if (currentIndex % 2 == 0) currentIndex + 1 else currentIndex - 1
            pathIndices.add(currentIndex % 2)

            if (siblingIndex < nodes[level].size) {
                siblings.add(nodes[level][siblingIndex])
            } else {
                siblings.add(BigInteger.ZERO)  // Padding for incomplete level
            }
            currentIndex /= 2
        }

        return LeanIMTProof(
            root = root,
            leaf = nodes[0][index],
            siblings = siblings,
            pathIndices = pathIndices,
        )
    }

    companion object {
        /**
         * Import a tree from serialized JSON string.
         * Format: {"nodes": [["leaf0", "leaf1", ...], ["node0", ...], ..., ["root"]]}
         */
        fun import(
            hashFn: (BigInteger, BigInteger) -> BigInteger,
            serialized: String,
        ): LeanIMT {
            val tree = LeanIMT(hashFn)
            val json = Json.parseToJsonElement(serialized).jsonObject
            val nodesArray = json["nodes"]?.jsonArray
                ?: throw IllegalArgumentException("Missing 'nodes' in serialized tree")

            for (level in nodesArray) {
                val levelNodes = level.jsonArray.map { it.jsonPrimitive.content.toBigInteger() }
                tree.nodes.add(levelNodes.toMutableList())
            }
            return tree
        }
    }
}

data class LeanIMTProof(
    val root: BigInteger,
    val leaf: BigInteger,
    val siblings: List<BigInteger>,
    val pathIndices: List<Int>,
)

`generateMerkleProof` wrapper (matches TypeScript API)

/**
 * Generate Merkle proof padded to a fixed depth.
 * Port of generateMerkleProof from common/src/utils/trees.ts
 */
fun generateMerkleProof(
    tree: LeanIMT,
    index: Int,
    maxLeafDepth: Int,
): PaddedMerkleProof {
    val proof = tree.generateProof(index)

    // Pad siblings and path to maxLeafDepth
    val paddedSiblings = proof.siblings.toMutableList()
    val paddedPath = proof.pathIndices.toMutableList()
    while (paddedSiblings.size < maxLeafDepth) {
        paddedSiblings.add(BigInteger.ZERO)
        paddedPath.add(0)
    }

    return PaddedMerkleProof(
        root = proof.root,
        siblings = paddedSiblings,
        path = paddedPath,
        leafDepth = proof.siblings.size,
    )
}

data class PaddedMerkleProof(
    val root: BigInteger,
    val siblings: List<BigInteger>,
    val path: List<Int>,
    val leafDepth: Int,
)

Testing

class LeanIMTTest {
    private val hashFn = { a: BigInteger, b: BigInteger -> poseidon2(a, b) }

    @Test
    fun `import and indexOf finds existing leaf`() {
        // Serialize a small tree in TypeScript, import here
        val serialized = """{"nodes":[["1","2","3","4"],["${poseidon2(1.bi, 2.bi)}","${poseidon2(3.bi, 4.bi)}"],["${poseidon2(poseidon2(1.bi, 2.bi), poseidon2(3.bi, 4.bi))}"]]}"""
        val tree = LeanIMT.import(hashFn, serialized)

        assertEquals(0, tree.indexOf(BigInteger.ONE))
        assertEquals(2, tree.indexOf(3.toBigInteger()))
        assertEquals(-1, tree.indexOf(99.toBigInteger()))
    }

    @Test
    fun `generateProof creates valid inclusion proof`() {
        // Import tree, generate proof, verify manually
        val tree = LeanIMT.import(hashFn, KNOWN_TREE_JSON)
        val proof = tree.generateProof(0)

        // Verify: hash up the path and check root matches
        var current = proof.leaf
        for (i in proof.siblings.indices) {
            current = if (proof.pathIndices[i] == 0)
                hashFn(current, proof.siblings[i])
            else
                hashFn(proof.siblings[i], current)
        }
        assertEquals(tree.root, current)
    }

    @Test
    fun `import real commitment tree from staging API`() {
        // Use a snapshot of a real serialized tree for integration testing
        val tree = LeanIMT.import(hashFn, STAGING_COMMITMENT_TREE_SNAPSHOT)
        assertTrue(tree.size > 0)
        assertNotEquals(BigInteger.ZERO, tree.root)
    }
}

5. Sparse Merkle Tree (SMT)

Port of @openpassport/zk-kit-smt. Used for OFAC sanctions list checking.

/**
 * Sparse Merkle Tree — key-value tree supporting membership and non-membership proofs.
 *
 * Hash function takes 2 children (internal nodes) or 3 elements (leaf: key, value, 1).
 * Tree depth is fixed (OFAC_TREE_LEVELS = 64).
 *
 * Used for OFAC sanctions checking:
 *   - nameAndDob tree
 *   - nameAndYob tree
 *   - passportNoAndNationality tree (passport only)
 */
class SparseMerkleTree(
    private val hashFn: (List<BigInteger>) -> BigInteger,
    private val bigNumbers: Boolean = true,
) {
    private val nodes: MutableMap<String, BigInteger> = mutableMapOf()
    private val entries: MutableMap<String, Pair<BigInteger, BigInteger>> = mutableMapOf()
    var root: BigInteger = BigInteger.ZERO
        private set

    fun add(key: BigInteger, value: BigInteger) { /* ... */ }

    /**
     * Create a membership or non-membership proof.
     *
     * @return SmtProof with entry, closest leaf, siblings, root, and membership flag
     */
    fun createProof(key: BigInteger): SmtProof { /* ... */ }

    companion object {
        fun import(hashFn: (List<BigInteger>) -> BigInteger, serialized: String): SparseMerkleTree {
            // Deserialize from JSON
        }
    }
}

data class SmtProof(
    val entry: Pair<BigInteger, BigInteger>,         // (key, value) being proven
    val matchingEntry: Pair<BigInteger, BigInteger>?, // Closest existing entry (non-membership)
    val siblings: List<BigInteger>,
    val root: BigInteger,
    val membership: Boolean,                          // true = member, false = non-member
)

`generateSMTProof` wrapper

/**
 * Generate SMT proof padded to OFAC_TREE_LEVELS.
 * Port of generateSMTProof from common/src/utils/trees.ts
 */
fun generateSMTProof(
    smt: SparseMerkleTree,
    leaf: BigInteger,
): PaddedSmtProof {
    val proof = smt.createProof(leaf)

    // Pad siblings to OFAC_TREE_LEVELS, reversed
    val paddedSiblings = proof.siblings.reversed().toMutableList()
    while (paddedSiblings.size < OFAC_TREE_LEVELS) {
        paddedSiblings.add(BigInteger.ZERO)
    }

    return PaddedSmtProof(
        root = proof.root,
        closestLeaf = if (proof.matchingEntry != null)
            listOf(proof.matchingEntry.first, proof.matchingEntry.second)
        else
            listOf(BigInteger.ZERO, BigInteger.ZERO),
        siblings = paddedSiblings,
        leafDepth = proof.siblings.size,
    )
}

6. OFAC Leaf Generation

Port of leaf generation functions from common/src/utils/trees.ts.

object LeafGenerators {
    /**
     * Generate name + DOB leaf for OFAC SMT.
     * name: 39 MRZ characters (passport) or 30 (ID card)
     * dob: 6 MRZ characters (YYMMDD)
     *
     * Hash: poseidon3(nameHash, poseidon6(dob[0..5]))
     * Where nameHash = poseidon3(poseidon13(name[0..12]), poseidon13(name[13..25]), poseidon13(name[26..38]))
     */
    fun getNameDobLeaf(name: List<BigInteger>, dob: List<BigInteger>): BigInteger {
        val nameHash = getNameLeaf(name)
        val dobHash = poseidon(dob.take(6))  // poseidon6
        return poseidon3(nameHash, dobHash, BigInteger.ZERO)  // Or appropriate combination
    }

    /**
     * Generate name leaf hash.
     * Passport (39 chars): 3 chunks of 13 → poseidon13 each → poseidon3 combine
     * ID card (30 chars): 3 chunks of 10 → poseidon10 each → poseidon3 combine
     */
    fun getNameLeaf(name: List<BigInteger>): BigInteger {
        val chunkSize = if (name.size <= 30) 10 else 13
        val chunks = name.chunked(chunkSize)
        val chunkHashes = chunks.map { poseidon(it) }
        return poseidon(chunkHashes)
    }

    fun getNameYobLeaf(name: List<BigInteger>, yob: List<BigInteger>): BigInteger {
        val nameHash = getNameLeaf(name)
        val yobHash = poseidon(yob.take(2))  // poseidon2
        return poseidon3(nameHash, yobHash, BigInteger.ZERO)
    }

    fun getPassportNumberAndNationalityLeaf(
        passportNumber: List<BigInteger>,
        nationality: List<BigInteger>,
    ): BigInteger {
        // poseidon12: 9 passport digits + 3 nationality chars
        return poseidon(passportNumber.take(9) + nationality.take(3))
    }

    fun getCountryLeaf(countryFrom: List<BigInteger>, countryTo: List<BigInteger>): BigInteger {
        return poseidon(countryFrom.take(3) + countryTo.take(3))  // poseidon6
    }
}

7. MRZ Formatter

Port of formatMrz from common/src/utils/passports/format.ts.

object MrzFormatter {
    /**
     * Format raw MRZ string into DER/TLV-encoded byte array for DG1 hashing.
     *
     * Prepends ASN.1 tags:
     *   0x61 (DG1 tag) | length | 0x5F 0x1F (MRZ_INFO tag) | MRZ length | MRZ bytes
     *
     * @param mrz Raw MRZ string (88 chars for passport, 90 for ID card)
     * @return Byte array with TLV encoding
     */
    fun format(mrz: String): List<Int> {
        val mrzBytes = mrz.map { it.code }.toMutableList()

        when (mrz.length) {
            88 -> {
                mrzBytes.add(0, 88)      // MRZ data length
                mrzBytes.add(0, 0x1F)    // MRZ_INFO tag byte 2
                mrzBytes.add(0, 0x5F)    // MRZ_INFO tag byte 1
                mrzBytes.add(0, 91)      // Total content length
                mrzBytes.add(0, 0x61)    // DG1 tag
            }
            90 -> {
                mrzBytes.add(0, 90)
                mrzBytes.add(0, 0x1F)
                mrzBytes.add(0, 0x5F)
                mrzBytes.add(0, 93)
                mrzBytes.add(0, 0x61)
            }
            else -> throw IllegalArgumentException("Unsupported MRZ length: ${mrz.length}")
        }

        return mrzBytes
    }
}

Testing

class MrzFormatterTest {
    @Test
    fun `format passport MRZ adds correct TLV tags`() {
        val mrz = "P<FRADUPONT<<JEAN<PIERRE<<<<<<<<<<<<<<<<<<<<<12345678<6FRA8001014M3001011<<<<<<<<<<<<<<02"
        assertEquals(88, mrz.length)
        val formatted = MrzFormatter.format(mrz)
        assertEquals(93, formatted.size)  // 5 header bytes + 88 MRZ bytes
        assertEquals(0x61, formatted[0])  // DG1 tag
        assertEquals(0x5F, formatted[2])  // MRZ_INFO tag
        assertEquals(0x1F, formatted[3])
    }
}

8. Commitment Generator

Port of generateCommitment from common/src/utils/passports/passport.ts.

object CommitmentGenerator {
    /**
     * Generate commitment hash for passport/ID document.
     *
     * commitment = poseidon5(secret, attestation_id, dg1_packed_hash, eContent_packed_hash, dsc_hash)
     *
     * @param secret User's secret (decimal string)
     * @param attestationId "1" (passport), "2" (ID card), "3" (aadhaar), "4" (kyc)
     * @param passportData Parsed passport with MRZ, eContent, parsed certificates
     * @return Commitment as BigInteger
     */
    fun generate(
        secret: String,
        attestationId: String,
        mrz: String,
        eContent: ByteArray,
        eContentHashFunction: String,
        dscParsed: CertificateData,
        cscaParsed: CertificateData,
    ): BigInteger {
        // 1. Hash formatted MRZ
        val mrzBytes = MrzFormatter.format(mrz)
        val dg1PackedHash = packBytesAndPoseidon(mrzBytes)

        // 2. Hash eContent with the document's hash algorithm, then pack
        val eContentShaBytes = sha(eContentHashFunction, eContent)
        val eContentPackedHash = packBytesAndPoseidon(eContentShaBytes.map { it.toInt() and 0xFF })

        // 3. Compute DSC tree leaf
        val dscHash = DscLeaf.getLeafDscTree(dscParsed, cscaParsed)

        // 4. Poseidon-5 commitment
        return poseidon5(listOf(
            secret.toBigInteger(),
            attestationId.toBigInteger(),
            dg1PackedHash,
            eContentPackedHash,
            dscHash,
        ))
    }
}

9. DSC Tree Leaf

Port of getLeafDscTree from common/src/utils/trees.ts.

object DscLeaf {
    /**
     * Compute DSC tree leaf from parsed DSC and CSCA certificates.
     *
     * leaf = poseidon2(dscLeaf, cscaLeaf)
     * where:
     *   dscLeaf = poseidon2(packBytesAndPoseidon(shaPad(tbsBytes, maxDscBytes)), tbsLength)
     *   cscaLeaf = poseidon2(packBytesAndPoseidon(zeroPad(tbsBytes, maxCscaBytes)), tbsLength)
     */
    fun getLeafDscTree(dscParsed: CertificateData, cscaParsed: CertificateData): BigInteger {
        val dscLeaf = getLeaf(dscParsed, CertType.DSC)
        val cscaLeaf = getLeaf(cscaParsed, CertType.CSCA)
        return poseidon2(dscLeaf, cscaLeaf)
    }

    private fun getLeaf(cert: CertificateData, type: CertType): BigInteger {
        val tbsBytes = cert.tbsBytes
        val maxBytes = if (type == CertType.DSC) MAX_DSC_BYTES else MAX_CSCA_BYTES

        val padded = if (type == CertType.DSC) {
            // DSC: SHA-pad the TBS bytes
            val (paddedBytes, _) = ShaPad.pad(cert.hashAlgorithm)(tbsBytes, maxBytes)
            paddedBytes
        } else {
            // CSCA: Zero-pad the TBS bytes
            val result = tbsBytes.toMutableList()
            while (result.size < maxBytes) result.add(0)
            result
        }

        val hash = packBytesAndPoseidon(padded)
        return poseidon2(hash, tbsBytes.size.toBigInteger())
    }

    private enum class CertType { DSC, CSCA }
}

10. ASN.1 / X.509 Certificate Parser

Port of parseCertificateSimple from common/src/utils/certificate_parsing/.

This is the most complex non-crypto component. It needs a minimal ASN.1 DER parser.

/**
 * Minimal ASN.1 DER parser for X.509 certificate extraction.
 *
 * Only parses what we need:
 *   - TBS (To-Be-Signed) bytes
 *   - Public key (RSA modulus/exponent, ECDSA x/y/curve)
 *   - Signature algorithm OID
 *   - Subject Key Identifier (SKI) and Authority Key Identifier (AKI)
 *   - Validity dates
 *
 * NOT a general-purpose ASN.1 library — just enough for passport certificates.
 */
object Asn1Parser {
    /**
     * Parse a DER-encoded byte array into an ASN.1 element tree.
     */
    fun parse(der: ByteArray): Asn1Element { /* ... */ }

    /**
     * Extract TBS (To-Be-Signed) bytes from a certificate DER.
     * The TBS is the first SEQUENCE inside the outer SEQUENCE.
     */
    fun extractTbs(certDer: ByteArray): ByteArray { /* ... */ }
}

sealed class Asn1Element {
    data class Sequence(val elements: List<Asn1Element>) : Asn1Element()
    data class Integer(val value: BigInteger) : Asn1Element()
    data class BitString(val bytes: ByteArray, val unusedBits: Int) : Asn1Element()
    data class OctetString(val bytes: ByteArray) : Asn1Element()
    data class ObjectIdentifier(val oid: String) : Asn1Element()
    data class Utf8String(val value: String) : Asn1Element()
    data class PrintableString(val value: String) : Asn1Element()
    data class UtcTime(val value: String) : Asn1Element()
    data class GeneralizedTime(val value: String) : Asn1Element()
    data class ContextSpecific(val tag: Int, val bytes: ByteArray) : Asn1Element()
    data class Unknown(val tag: Int, val bytes: ByteArray) : Asn1Element()
}

/**
 * Parse X.509 certificate PEM into structured CertificateData.
 *
 * Port of parseCertificateSimple from common/src/utils/certificate_parsing/
 */
object X509CertificateParser {
    fun parse(pem: String): CertificateData {
        val der = pemToDer(pem)
        val root = Asn1Parser.parse(der) as Asn1Element.Sequence

        val tbs = root.elements[0] as Asn1Element.Sequence
        val tbsBytes = Asn1Parser.extractTbs(der)

        val signatureAlgorithmOid = extractSignatureAlgorithmOid(tbs)
        val publicKeyInfo = extractPublicKeyInfo(tbs)
        val validity = extractValidity(tbs)
        val extensions = extractExtensions(tbs)
        val ski = extractSki(extensions)
        val aki = extractAki(extensions)

        return CertificateData(
            tbsBytes = tbsBytes.map { it.toInt() and 0xFF },
            tbsBytesLength = tbsBytes.size.toString(),
            signatureAlgorithm = OidResolver.resolveSignatureAlgorithm(signatureAlgorithmOid),
            hashAlgorithm = OidResolver.resolveHashAlgorithm(signatureAlgorithmOid),
            publicKeyDetails = publicKeyInfo,
            subjectKeyIdentifier = ski ?: "",
            authorityKeyIdentifier = aki ?: "",
            validity = validity,
            rawPem = pem,
        )
    }

    private fun pemToDer(pem: String): ByteArray {
        val base64 = pem.lines()
            .filter { !it.startsWith("-----") }
            .joinToString("")
        return base64Decode(base64)
    }
}

OID Resolution

object OidResolver {
    private val signatureAlgorithms = mapOf(
        "1.2.840.113549.1.1.5" to "rsa",        // sha1WithRSAEncryption
        "1.2.840.113549.1.1.11" to "rsa",       // sha256WithRSAEncryption
        "1.2.840.113549.1.1.12" to "rsa",       // sha384WithRSAEncryption
        "1.2.840.113549.1.1.13" to "rsa",       // sha512WithRSAEncryption
        "1.2.840.113549.1.1.10" to "rsapss",    // RSASSA-PSS
        "1.2.840.10045.4.1" to "ecdsa",         // ecdsaWithSHA1
        "1.2.840.10045.4.3.2" to "ecdsa",       // ecdsaWithSHA256
        "1.2.840.10045.4.3.3" to "ecdsa",       // ecdsaWithSHA384
        "1.2.840.10045.4.3.4" to "ecdsa",       // ecdsaWithSHA512
    )

    private val curves = mapOf(
        "1.2.840.10045.3.1.7" to "secp256r1",
        "1.3.132.0.34" to "secp384r1",
        "1.3.132.0.35" to "secp521r1",
        "1.3.36.3.3.2.8.1.1.7" to "brainpoolP256r1",
        "1.3.36.3.3.2.8.1.1.9" to "brainpoolP320r1",
        "1.3.36.3.3.2.8.1.1.11" to "brainpoolP384r1",
        "1.3.36.3.3.2.8.1.1.13" to "brainpoolP512r1",
    )

    fun resolveSignatureAlgorithm(oid: String): String = signatureAlgorithms[oid] ?: "unknown"
    fun resolveCurve(oid: String): String = curves[oid] ?: "unknown"
    fun resolveHashAlgorithm(sigOid: String): String { /* map OID → sha256, etc */ }
}

Testing

class X509CertificateParserTest {
    @Test
    fun `parse RSA DSC certificate`() {
        val cert = X509CertificateParser.parse(KNOWN_RSA_DSC_PEM)
        assertEquals("rsa", cert.signatureAlgorithm)
        assertEquals("sha256", cert.hashAlgorithm)
        assertNotNull(cert.publicKeyDetails as? PublicKeyDetailsRSA)
        assertTrue(cert.tbsBytes.isNotEmpty())
    }

    @Test
    fun `parse ECDSA DSC certificate`() {
        val cert = X509CertificateParser.parse(KNOWN_ECDSA_DSC_PEM)
        assertEquals("ecdsa", cert.signatureAlgorithm)
        val ecDetails = cert.publicKeyDetails as PublicKeyDetailsECDSA
        assertEquals("secp256r1", ecDetails.curve)
        assertTrue(ecDetails.x.isNotEmpty())
        assertTrue(ecDetails.y.isNotEmpty())
    }

    @Test
    fun `extract SKI and AKI`() {
        val cert = X509CertificateParser.parse(KNOWN_DSC_PEM)
        assertTrue(cert.subjectKeyIdentifier.isNotEmpty())
        assertTrue(cert.authorityKeyIdentifier.isNotEmpty())
    }

    @Test
    fun `TBS bytes match TypeScript output`() {
        // Compare tbsBytes from Kotlin vs TypeScript for the same certificate
        val cert = X509CertificateParser.parse(TEST_CERT_PEM)
        assertEquals(EXPECTED_TBS_BYTES, cert.tbsBytes)
    }
}

11. Passport Data Parser

Port of initPassportDataParsing and parsePassportData.

object PassportDataParser {
    /**
     * Parse raw NFC scan output into structured PassportData with metadata.
     *
     * Extracts:
     *   - DG1 hash function and location in eContent
     *   - eContent hash algorithm
     *   - Signed attributes hash algorithm
     *   - Signature algorithm (RSA, ECDSA, RSA-PSS) with key details
     *   - CSCA certificate (if found via SKI lookup)
     *   - Country code from MRZ
     *
     * Port of initPassportDataParsing + parsePassportData
     */
    fun parse(
        mrz: String,
        eContent: ByteArray,
        signedAttr: ByteArray,
        dscPem: String,
        skiPem: Map<String, String>? = null,
    ): ParsedPassportData {
        val dscParsed = X509CertificateParser.parse(dscPem)

        // Extract country code from MRZ (positions 2-4 for passport)
        val countryCode = mrz.substring(2, 5).replace("<", "")

        // Find DG1 hash in eContent (try each hash algorithm)
        val (dg1HashFunction, dg1HashOffset, dg1HashSize) = findDg1HashInEContent(mrz, eContent)

        // Determine eContent hash algorithm
        val eContentHashFunction = findEContentHashFunction(eContent, signedAttr)

        // Determine signature algorithm (may require brute-force detection)
        val signedAttrHashFunction = findSignedAttrHashFunction(signedAttr)

        // Parse DSC certificate for algorithm details
        val signatureAlgorithm = dscParsed.signatureAlgorithm
        val curveOrExponent = when (val pk = dscParsed.publicKeyDetails) {
            is PublicKeyDetailsRSA -> pk.exponent
            is PublicKeyDetailsECDSA -> pk.curve
            is PublicKeyDetailsRSAPSS -> pk.exponent
        }

        // Look up CSCA by SKI
        val aki = dscParsed.authorityKeyIdentifier
        val cscaPem = skiPem?.get(aki)
        val cscaParsed = cscaPem?.let { X509CertificateParser.parse(it) }

        return ParsedPassportData(
            passportMetadata = PassportMetadata(
                countryCode = countryCode,
                cscaFound = cscaParsed != null,
                dg1HashFunction = dg1HashFunction,
                eContentHashFunction = eContentHashFunction,
                signedAttrHashFunction = signedAttrHashFunction,
                signatureAlgorithm = signatureAlgorithm,
                curveOrExponent = curveOrExponent,
                // ... other fields
            ),
            dscParsed = dscParsed,
            cscaParsed = cscaParsed,
        )
    }
}

12. Selector Generator

Port of getSelectorDg1 from common/src/utils/circuits/registerInputs.ts. (Moved here from proving client spec since it's pure data mapping.)

object SelectorGenerator {
    private val passportPositions = mapOf(
        "issuing_state" to (2..4),
        "name" to (5..43),
        "passport_number" to (44..52),
        "nationality" to (54..56),
        "date_of_birth" to (57..62),
        "gender" to (64..64),
        "expiry_date" to (65..70),
    )

    private val idCardPositions = mapOf(
        "issuing_state" to (2..4),
        "passport_number" to (5..13),
        "date_of_birth" to (30..35),
        "gender" to (37..37),
        "expiry_date" to (38..43),
        "nationality" to (45..47),
        "name" to (60..89),
    )

    /**
     * Generate DG1 selector bit array marking which MRZ bytes to reveal.
     *
     * @param category passport (88 bits) or id_card (90 bits)
     * @param revealedAttributes List of attribute names to reveal
     * @return List of "0" and "1" strings
     */
    fun getDg1Selector(category: String, revealedAttributes: List<String>): List<String> {
        val size = if (category == "id_card") 90 else 88
        val positions = if (category == "id_card") idCardPositions else passportPositions
        val selector = MutableList(size) { "0" }

        for (attr in revealedAttributes) {
            if (attr in listOf("ofac", "excludedCountries", "minimumAge")) continue
            positions[attr]?.let { range ->
                for (i in range) selector[i] = "1"
            }
        }
        return selector
    }
}

Constants

object Constants {
    // Tree depths
    const val DSC_TREE_DEPTH = 21
    const val CSCA_TREE_DEPTH = 12
    const val COMMITMENT_TREE_DEPTH = 33
    const val OFAC_TREE_LEVELS = 64

    // Max padded sizes (bytes)
    const val MAX_DSC_BYTES = 4000
    const val MAX_CSCA_BYTES = 4000
    const val MAX_PADDED_ECONTENT_LEN_SHA256 = 512
    const val MAX_PADDED_SIGNED_ATTR_LEN_SHA256 = 256

    // RSA word sizes for circuit inputs
    const val N_DSC = 32; const val K_DSC = 64           // 2048-bit
    const val N_DSC_3072 = 32; const val K_DSC_3072 = 96 // 3072-bit
    const val N_DSC_4096 = 32; const val K_DSC_4096 = 128 // 4096-bit
    const val N_DSC_ECDSA = 64; const val K_DSC_ECDSA = 4 // P-256

    // Attestation IDs
    const val PASSPORT_ATTESTATION_ID = "1"
    const val ID_CARD_ATTESTATION_ID = "2"
    const val AADHAAR_ATTESTATION_ID = "3"
    const val KYC_ATTESTATION_ID = "4"
}

Chunking Guide

Chunk 6A: Poseidon Hash + Byte Packing (start here, hardest)

Goal: Working Poseidon hash that produces identical outputs to poseidon-lite.

Steps:

Implement BigIntField.kt — modular arithmetic over BN254 prime
Extract round constants and mixing matrices from poseidon-lite npm package → PoseidonConstants.kt
Implement Poseidon.kt — core algorithm (pow5, addRoundConstants, mix)
Implement convenience functions (poseidon2 through poseidon16)
Implement BytePacking.kt — packBytesArray, splitToWords, etc.
Implement FlexiblePoseidon.kt — flexiblePoseidon, customHasher, packBytesAndPoseidon
Test: Compare Poseidon outputs against TypeScript for 50+ test vectors covering all variants (poseidon1 through poseidon16)
Test: packBytesAndPoseidon with known byte arrays matches TypeScript
Validate: ./gradlew :shared:jvmTest

Test vector generation: Create a TypeScript script that outputs test vectors:

// scripts/generate-poseidon-vectors.ts
import { poseidon1, poseidon2, ..., poseidon16 } from 'poseidon-lite'
const vectors = [
  { fn: 'poseidon2', inputs: [1n, 2n], output: poseidon2([1n, 2n]).toString() },
  { fn: 'poseidon2', inputs: [0n, 0n], output: poseidon2([0n, 0n]).toString() },
  // ... edge cases: max field element, zero, large values
]
console.log(JSON.stringify(vectors, null, 2))

This is the highest-risk chunk — if Poseidon outputs don't match, nothing downstream works.

Chunk 6B: SHA Padding + MRZ Formatter

Goal: Circuit-compatible SHA padding and MRZ formatting.

Steps:

Implement ShaPad.kt — shaPad, sha384_512Pad
Implement MrzFormatter.kt — formatMrz with TLV encoding
Implement Sha.kt — SHA-1/256/384/512 (pure Kotlin or use kotlinx-io / third-party)
Test: SHA padding matches TypeScript for known inputs
Test: formatMrz produces correct byte arrays for 88-char and 90-char MRZ strings
Validate: ./gradlew :shared:jvmTest

Chunk 6C: LeanIMT + Sparse Merkle Tree

Goal: Tree data structures with import, lookup, and proof generation.

Steps:

Implement LeanIMT.kt — import from JSON, indexOf, generateProof
Implement MerkleProof.kt — padded proof generation wrapper
Implement SparseMerkleTree.kt — import, add, createProof
Implement LeafGenerators.kt — all OFAC leaf functions
Implement TreeConstants.kt — depth constants
Test: Import a snapshot of a real commitment tree, verify root hash
Test: indexOf finds known leaves, returns -1 for unknown
Test: generateProof creates verifiable proofs (hash up the path = root)
Test: SMT membership and non-membership proofs
Test: Leaf generators produce same values as TypeScript
Validate: ./gradlew :shared:jvmTest

Test fixture strategy: Snapshot real trees from the staging API. Store as resource files in commonTest/resources/.

Chunk 6D: ASN.1 Parser + Certificate Parser

Goal: Parse X.509 certificates from PEM into structured data.

Steps:

Implement Asn1Parser.kt — minimal DER parser (SEQUENCE, INTEGER, BIT STRING, OID, OCTET STRING, context-specific tags)
Implement OidResolver.kt — OID → algorithm/curve name mapping
Implement X509CertificateParser.kt — parseCertificateSimple
Implement CscaLookup.kt — SKI → CSCA PEM mapping
Implement SignatureExtractor.kt — extract r,s from DER ECDSA signatures
Test: Parse known RSA DSC certificate → verify modulus, exponent, TBS bytes
Test: Parse known ECDSA DSC certificate → verify x, y, curve
Test: Parse known RSA-PSS certificate → verify hash, mgf, salt length
Test: SKI/AKI extraction matches TypeScript
Test: TBS bytes match TypeScript output byte-for-byte
Validate: ./gradlew :shared:jvmTest

Test certificates: Use mock certificates from common/src/constants/mockCertificates.ts and real DSC certificates from the staging API.

Chunk 6E: Passport Data Parser + Commitment/Nullifier

Goal: End-to-end passport parsing and commitment generation.

Steps:

Implement PassportDataParser.kt — initPassportDataParsing equivalent
Implement CommitmentGenerator.kt — generateCommitment
Implement NullifierGenerator.kt — generateNullifier
Implement DscLeaf.kt — getLeafDscTree
Implement SelectorGenerator.kt — getDg1Selector
Test: Parse mock passport data → verify all metadata fields match TypeScript
Test: Generate commitment for known passport + secret → matches TypeScript
Test: Generate nullifier for known passport → matches TypeScript
Test: DSC tree leaf hash matches TypeScript
Test: Selector bits for known disclosure flags match TypeScript
Integration test: Parse mock passport → generate commitment → look up in imported tree
Validate: ./gradlew :shared:jvmTest

This chunk proves the entire pipeline works: raw data → parsed metadata → hashed commitment → tree lookup.

Testing Strategy

Test Vector Generation

Create a one-time TypeScript script (scripts/generate-kmp-test-vectors.ts) that outputs all needed test vectors:

// Run: npx ts-node scripts/generate-kmp-test-vectors.ts > test-vectors.json

import { poseidon2, poseidon5 } from 'poseidon-lite'
import { LeanIMT } from '@openpassport/zk-kit-lean-imt'
import { genAndInitMockPassportData } from '../common/src/utils/passports/mock'
import { generateCommitment } from '../common/src/utils/passports/passport'
import { packBytesAndPoseidon } from '../common/src/utils/hash'
import { formatMrz } from '../common/src/utils/passports/format'
import { parseCertificateSimple } from '../common/src/utils/certificate_parsing'

const vectors = {
  poseidon: [
    { inputs: ['1', '2'], output: poseidon2([1n, 2n]).toString() },
    // ... 50+ vectors for all poseidon1-16
  ],
  packBytesAndPoseidon: [
    { bytes: [1, 2, 3, 4, 5], output: packBytesAndPoseidon([1, 2, 3, 4, 5]).toString() },
    // ... various lengths
  ],
  formatMrz: [
    { mrz: "P<FRA...", output: formatMrz("P<FRA...") },
  ],
  commitment: [
    {
      secret: "12345",
      attestationId: "1",
      mrz: "P<FRA...",
      output: generateCommitment("12345", "1", mockPassport).toString()
    },
  ],
  certificates: [
    { pem: "-----BEGIN CERTIFICATE-----...", tbsBytes: [...], ski: "...", aki: "..." },
  ],
}

console.log(JSON.stringify(vectors, null, 2))

Store output in packages/kmp-sdk/shared/src/commonTest/resources/test-vectors.json. Load in tests.

Test Categories

Category	Count	What's Verified
Poseidon hash	~60 tests	All 16 variants, edge cases (zero, max field, overflow)
Byte packing	~15 tests	packBytes, splitToWords, roundtrips
SHA padding	~10 tests	SHA-256 and SHA-384 padding correctness
MRZ formatting	~5 tests	88-char passport, 90-char ID card, error cases
LeanIMT	~15 tests	Import, indexOf, generateProof, root verification
SMT	~10 tests	Import, membership proof, non-membership proof
Leaf generators	~10 tests	Name, DOB, country, passport number leaves
ASN.1 parser	~10 tests	Known DER structures, edge cases
Certificate parser	~15 tests	RSA, ECDSA, RSA-PSS, SKI/AKI extraction, TBS bytes
Passport parser	~10 tests	Metadata extraction for various algo combos
Commitment	~10 tests	Known passport + secret → expected commitment
Nullifier	~5 tests	Known passport → expected nullifier
DSC leaf	~5 tests	Known certificates → expected leaf hash
Selector	~10 tests	All attribute combos for passport and ID card
Total	~190 tests

Cross-Platform Verification

Run the same commonTest suite on all targets:

./gradlew :shared:jvmTest          # Fast iteration
./gradlew :shared:iosSimulatorArm64Test  # Verify iOS
# Future: ./gradlew :shared:jsTest    # Verify browser extension compatibility

Dependencies

Build Dependencies

commonMain.dependencies {
    implementation(libs.kotlinx.serialization.json)  // Already present
    // No other dependencies — everything is pure Kotlin
}

commonTest.dependencies {
    implementation(libs.kotlin.test)
    implementation(libs.kotlinx.coroutines.test)  // Already present
}

No additional library dependencies. This is intentionally zero-dependency (beyond kotlinx-serialization for JSON parsing of tree data). SHA hashing can be implemented in pure Kotlin (~200 lines for SHA-256) to avoid any platform dependency.

If SHA performance matters, add expect/actual later — but for correctness-first, pure Kotlin is simpler.

Spec Dependencies

None — this is the leaf dependency
SPEC-PROVING-CLIENT.md depends on this (chunks 4D, 4E, 4F use Poseidon, trees, commitment)
SPEC-MINIPAY-SAMPLE.md depends on this indirectly (via proving client)
Future browser extension depends on this directly

Key TypeScript Reference Files

TypeScript File	What to Port	Kotlin Target
`common/src/utils/hash.ts`	Poseidon wrappers, SHA, packBytesAndPoseidon	`hash/` package
`common/src/utils/bytes.ts`	packBytes, splitToWords, hexToDecimal	`math/BytePacking.kt`
`common/src/utils/shaPad.ts`	SHA-256 and SHA-384 padding	`hash/ShaPad.kt`
`common/src/utils/trees.ts`	LeanIMT operations, SMT operations, leaf generators, proof generation	`trees/` package
`common/src/utils/passports/passport.ts`	generateCommitment, generateNullifier, formatMrz	`passport/` package
`common/src/utils/passports/format.ts`	formatMrz, DG1 formatting	`passport/MrzFormatter.kt`
`common/src/utils/passports/passport_parsing/parsePassportData.ts`	Metadata extraction	`passport/PassportDataParser.kt`
`common/src/utils/certificate_parsing/parseCertificateSimple.ts`	X.509 parsing	`certificate/X509CertificateParser.kt`
`common/src/utils/certificate_parsing/oids.ts`	OID resolution	`certificate/OidResolver.kt`
`common/src/constants/constants.ts`	Tree depths, max sizes, attestation IDs	`constants/Constants.kt`
`common/src/constants/skiPem.ts`	SKI → CSCA PEM mapping	`constants/SkiPem.kt`
`poseidon-lite` (npm)	Poseidon algorithm + round constants	`hash/Poseidon.kt`, `hash/PoseidonConstants.kt`
`@openpassport/zk-kit-lean-imt` (npm)	LeanIMT data structure	`trees/LeanIMT.kt`
`@openpassport/zk-kit-smt` (npm)	Sparse Merkle Tree	`trees/SparseMerkleTree.kt`

53 KiB Raw Permalink Blame History Unescape Escape

Common KMP Library — Port @selfxyz/common Utilities to Pure Kotlin

Overview

Why Pure commonMain

Module Structure

Detailed Component Specs

1. Poseidon Hash

Field Prime

Algorithm

Round Constants

Convenience Functions

flexiblePoseidon and packBytesAndPoseidon

Testing

2. Byte Packing Utilities

Testing

3. SHA Padding

Testing

4. LeanIMT (Lean Incremental Merkle Tree)

generateMerkleProof wrapper (matches TypeScript API)

Testing

5. Sparse Merkle Tree (SMT)

generateSMTProof wrapper

6. OFAC Leaf Generation

7. MRZ Formatter

Testing

8. Commitment Generator

9. DSC Tree Leaf

10. ASN.1 / X.509 Certificate Parser

OID Resolution

Testing

11. Passport Data Parser

12. Selector Generator

Constants

Chunking Guide

Chunk 6A: Poseidon Hash + Byte Packing (start here, hardest)

Chunk 6B: SHA Padding + MRZ Formatter

Chunk 6C: LeanIMT + Sparse Merkle Tree

Chunk 6D: ASN.1 Parser + Certificate Parser

Chunk 6E: Passport Data Parser + Commitment/Nullifier

Testing Strategy

Test Vector Generation

Test Categories

Cross-Platform Verification

Dependencies

Build Dependencies

Spec Dependencies

Key TypeScript Reference Files

53 KiB

Raw Permalink Blame History

Common KMP Library — Port `@selfxyz/common` Utilities to Pure Kotlin

Why Pure `commonMain`

`flexiblePoseidon` and `packBytesAndPoseidon`

`generateMerkleProof` wrapper (matches TypeScript API)

`generateSMTProof` wrapper