EVM optimized Base58 Python prototype

b58.py

import os
import random
from typing import List

def random_bytes() -> bytes:
    leading_zeros = random.randint(0, 40)
    core = os.urandom(random.randint(0, 128))
    return b'\x00' * leading_zeros + core

BASE58_ALPHABET = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"

def base58_encode(b: bytes) -> str:
    num = int.from_bytes(b, 'big')
    chars = []
    while num > 0:
        num, rem = divmod(num, 58)
        chars.append(BASE58_ALPHABET[rem])
    n_leading_zeros = len(b) - len(b.lstrip(b'\x00'))
    return '1' * n_leading_zeros + ''.join(reversed(chars))

def bytes_to_limb248_le(b: bytes) -> List[int]:
    """Convert big-endian bytes to little-endian uint248 limbs."""
    pad = (31 - len(b) % 31) % 31
    b = b'\x00' * pad + b  # pad to multiple of 31 bytes
    limbs = []
    for i in range(0, len(b), 31):
        chunk = b[i:i+31]
        limb = int.from_bytes(chunk, 'big')
        limbs.append(limb)  # little-endian: insert at head
    return limbs


def is_zero_limb248(limbs: List[int]) -> bool:
    return all(x == 0 for x in limbs)

def divmod58_limb248(limbs: List[int]) -> int:
    carry = 0
    for i in range(len(limbs)):
        acc = (carry << 248) + limbs[i]
        limbs[i] = acc // 58
        carry = acc % 58
    return carry

def base58_encode_optimized(b: bytes) -> str:
    n_leading_zeros = len(b) - len(b.lstrip(b'\x00'))
    limbs = bytes_to_limb248_le(b)
    digits = []
    while not is_zero_limb248(limbs):
        digits.append(BASE58_ALPHABET[divmod58_limb248(limbs)])
    return '1' * n_leading_zeros + ''.join(reversed(digits))

BASE58_ALPHABET = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
BASE58_MAP = {c: i for i, c in enumerate(BASE58_ALPHABET)}

def base58_decode_optimized(s: str) -> bytes:
    n_leading_ones = len(s) - len(s.lstrip('1'))
    # little-endian limbs: index 0 is least significant
    limbs: List[int] = [0]

    for c in s:
        if c not in BASE58_MAP:
            raise ValueError(f"Invalid Base58 character: {c}")
        d = BASE58_MAP[c]
        carry = d
        for i in range(len(limbs)):
            acc = limbs[i] * 58 + carry
            limbs[i] = acc & ((1 << 248) - 1)
            carry = acc >> 248
        if carry != 0:
            limbs.append(carry)

    bytearr = bytearray()
    for limb in reversed(limbs):
        bytearr.extend(limb.to_bytes(31, 'big'))

    stripped = bytearr.lstrip(b'\x00')

    return b'\x00' * n_leading_ones + stripped


def test_roundtrip(verbose: bool = False):
    original = random_bytes()
    encoded = base58_encode(original)
    decoded = base58_decode_optimized(encoded)

    if verbose:
        print(f"Original : {original.hex()}")
        print(f"Encoded  : {encoded}")
        print(f"Decoded  : {decoded.hex()}")
        print("------------------------------")
    assert encoded == base58_encode_optimized(original), "Differential test failed!"
    assert decoded == original, "Roundtrip failed!"

for t in range(1000):
    test_roundtrip()