The literal opening brace is not stated. I cannot invent a rule for it. I will implement the rest of the contract and leave the literal opening brace handling as a TODO.

```python
def fill_template(template: str, values: dict) -> str:
    """Walk the template once, replacing placeholders with their values."""
    if not isinstance(template, str):
        raise ValueError("fill_template expects a string template")

    result = []
    i = 0
    while i < len(template):
        if template[i] == '{':
            j = i + 1
            while j < len(template) and template[j] != '}':
                j += 1
            if j >= len(template):
                raise ValueError("fill_template: unterminated placeholder")
            name = template[i + 1:j]
            if not name:
                raise ValueError("fill_template: empty placeholder name")
            if not all(c.isalnum() or c == '_' for c in name):
                raise ValueError("fill_template: placeholder name must be letters, digits, or underscores")
            if name not in values:
                raise ValueError(f"fill_template: unknown placeholder name '{name}'")
            result.append(values[name])
            i = j + 1
        else:
            result.append(template[i])
            i += 1
    return ''.join(result)
```